2802. Find The K-th Lucky Number

Medium

Problem Description

In this problem, we have two digits that are considered "lucky" – 4 and 7. A number is termed as a "lucky number" if and only if every digit in the number is either a 4 or a 7. We are given a task to find the k^th^ lucky number when all the lucky numbers are sorted in increasing order. We need to provide this lucky number as a string.

For instance, the first few lucky numbers are: 1st lucky number is "4" 2nd lucky number is "7" 3rd lucky number is "44" (and so on)

The challenge here is to calculate the k^th^ lucky number without generating all previous lucky numbers.

Intuition

To solve this problem, we can draw an analogy from binary numbers. If we replace every binary digit 0 with 4 and every binary digit 1 with 7, we get a system where each binary number corresponds to a lucky number. For example, binary 0 (which in our modified system would be "4"), binary 1 ("7"), binary 10 ("44"), binary 11 ("47") and so on.

To find the k^th^ lucky number, we follow a similar approach as we would finding the k^th^ number in binary. However, unlike a standard binary system where each position can be 0 or 1, we only have two digits 4 and 7, representing the two possible states at each position of a lucky number. We determine the length of our lucky number (in digits) by finding the smallest number n such that k is less than 2^n. This represents the level at which the k^th^ lucky number exists if we were to visualize all lucky numbers in a binary tree form.

Once we have the number of digits n, we can construct the lucky number from most significant digit to least significant digit, by checking if k is in the lower half (which would correspond to '4') or the upper half (which would correspond to '7') of the values for that digit's position—this is akin to deciding between 0 and 1 in binary representation. If it's in the upper half, we know this digit is ‘7’, and we subtract the size of the lower half (2^(n - 1)) from k to continue finding the rest of the digits. If it's in the lower half, we simply assign '4' to this current digit. We iterate this process until we have all n digits of our lucky number.

By approaching the problem in this manner, we efficiently calculate the k^th^ lucky number without the need to list or check all previous lucky numbers.

Solution Approach

The solution implements the intuition discussed above with a focus on optimizing the process. Here's the detailed explanation of the code step-by-step:

We start by initializing n to 1. This n variable will eventually indicate the number of digits in our k^th^ lucky number.
The first while loop checks how many digits the k^th^ lucky number will have. It works under the principle that there are 2^n lucky numbers with n digits (2^n - 1 possible combinations plus the all-4s combination). So, if k is greater than 2^n, k is not within the range of lucky numbers that have n digits. Therefore, we subtract 2^n from k and increment n by 1, and iterate until k is less than or equal to 2^n. This locates the correct 'level' of the binary-tree-like structure where our number sits.
Once we have the number of digits n, we initialize an empty list ans, which will store each digit of the k^th^ lucky number as we compute it.
The second while loop executes n times, decreasing n with each iteration. Each iteration of the loop decides one digit of the lucky number, starting from most significant to least significant. The conditional within this loop if k <= 1 << n is checking whether k fits in the lower half of the range for the current digit (which would correspond to '4'). If so, '4' is appended to ans. Otherwise, '7' is appended, and k is decremented by 2^(n-1) or 1 << n to reflect that we're now looking in the upper half of the range for the next digit.
After the loop completes, ans holds the digits of our k^th^ lucky number in order. We finally return the number as a string by joining each element of the list with "".join(ans).

This implementation uses a list (ans) as the primary data structure to build the lucky number and follows a binary search pattern to decide each digit of the lucky number, improving the efficiency by avoiding unnecessary computation that would come from generating all previous lucky numbers.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using an example. We want to find the 5th lucky number.

Initialize n to 1, because every lucky number has at least one digit.
Begin the first while loop to find the number of digits our 5th lucky number will have. We know there are 2^n lucky numbers for each digit length. Initially, n is 1, and 2^n is 2, which is less than 5. So we increment n to 2, and now 2^n is 4, which is still less than 5. Incrementing n once more gives us 2^n as 8, which is greater than 5. So, we stop here and know that our 5th lucky number has 3 digits.
We now start with k = 5 and n = 3. Initialize an empty list ans to store the digits.
Enter the second while loop, which will run three times (since our lucky number has 3 digits):
- In the first iteration, 1 << n equals 1 << 3 which equals 8. This is greater than k (5), so k is in the lower half. We append '4' to ans and do not change k.
- In the second iteration, we decrement n to 2. Now 1 << n is 4, which is less than k. Hence, k is in the upper half, and we need to subtract 1 << (n-1) (which is 2) from k. k becomes 3, and we append '7' to ans.
- In the third and final iteration, n is decremented to 1, making 1 << n equal to 2. k is 3, which is greater; therefore, we are again in the upper half. We subtract 1 << (n-1) from k, which is 1, making k now equal to 2. We append '7' to ans.
The second while loop completes and our list ans has the values ['4', '7', '7'].
We join these to form the 5th lucky number: "".join(ans) equals "477".

Therefore, the 5th lucky number is "477". This example clearly shows how the binary-like approach works by deciding one digit at a time, based on whether k is in the lower or upper half of the range for that digit.

Solution Implementation

1class Solution:
2    def kth_lucky_number(self, k: int) -> str:
3        # Initialize the number of digits to be considered to 1
4        num_digits = 1
5      
6        # Find the number of digits the kth lucky number must have
7        while k > (1 << num_digits):
8            # Decrease k by the count of lucky numbers with num_digits digits
9            k -= 1 << num_digits
10            # Increment the digit count as we're moving on to numbers with more digits
11            num_digits += 1
12      
13        # Initialize the answer as an empty list to hold the digits
14        answer_digits = []
15      
16        # Construct the kth lucky number by going through each digit place
17        while num_digits:
18            num_digits -= 1  # Decrement digits count as we build the number from high to low
19            if k <= (1 << num_digits):
20                # If k is within the range of the first half, append 4, as it is the smaller digit
21                answer_digits.append("4")
22            else:
23                # If k is in the second half, append 7 and adjust k accordingly
24                answer_digits.append("7")
25                k -= 1 << num_digits  # Decrement k as we have used one of the 7s
26      
27        # Join all the individual digits to form the kth lucky number and return it
28        return "".join(answer_digits)
29

1class Solution {
2    public String kthLuckyNumber(int k) {
3        // 'n' represents the number of digits in the lucky number
4        int n = 1;
5      
6        // Find the number of digits in the kth lucky number by comparing k with powers of 2
7        while (k > (1 << n)) {
8            k -= (1 << n);
9            ++n;
10        }
11      
12        // Build the kth lucky number starting with the most significant digit
13        StringBuilder ans = new StringBuilder();
14        while (n > 0) {
15            // Check the kth bit of n to decide whether to append '4' or '7'
16            // If k is in the first half of the range for the current digit length, append '4'
17            if (k <= (1 << (n - 1))) {
18                ans.append('4');
19            } else {
20                // If k is in the second half, append '7' and update k
21                ans.append('7');
22                k -= (1 << (n - 1));
23            }
24            n--;
25        }
26      
27        return ans.toString();
28    }
29}
30

1#include <string>
2
3class Solution {
4public:
5    // Function to find the kth lucky number where lucky numbers are 
6    // positive integers whose decimal representation contains only the digits 4 and 7.
7    std::string kthLuckyNumber(int k) {
8        // Start counting digits from 1
9        int numDigits = 1;
10
11        // Find the number of digits in the kth lucky number by using powers of 2
12        // Each additional digit doubles the count of lucky numbers available
13        while (k > (1 << numDigits)) {
14            k -= 1 << numDigits; // Subtract the number of numbers with `numDigits` digits
15            ++numDigits;         // Move to the next digit length
16        }
17
18        // Initialize an empty string to store the kth lucky number
19        std::string luckyNumber;
20
21        // Construct the lucky number digit by digit
22        while (numDigits--) {
23            // If the remaining k is less or equal to the number of lucky numbers with the current number of digits
24            if (k <= (1 << numDigits)) {
25                luckyNumber.push_back('4'); // A '4' is appended when k is in the first half within the current digit's range
26            } else {
27                luckyNumber.push_back('7'); // Otherwise, a '7' is appended
28                k -= 1 << numDigits;       // And we adjust k to reflect that we're now considering the second half range
29            }
30        }
31      
32        // Return the constructed lucky number as a string
33        return luckyNumber;
34    }
35};
36

1function kthLuckyNumber(k: number): string {
2    // Initialize counter 'n' which represents the number of binary digits.
3    let counter = 1;
4
5    // As long as 'k' is greater than '2^n', decrease 'k' by '2^n' and increment 'n'.
6    while (k > (1 << counter)) {
7        k -= 1 << counter;
8        ++counter;
9    }
10
11    // Initialize an array 'luckyNumbers' to store the lucky number digits.
12    const luckyNumbers: string[] = [];
13
14    // Build the lucky number by determining if each digit is a '4' or a '7'.
15    while (counter-- > 0) {
16        if (k <= (1 << counter)) {
17            // If 'k' is less than or equal to '2^n', the digit is '4'.
18            luckyNumbers.push('4');
19        } else {
20            // If 'k' is greater, the digit is '7' and we adjust 'k' accordingly.
21            luckyNumbers.push('7');
22            k -= 1 << counter;
23        }
24    }
25
26    // Join the digits and return the resulting lucky number as a string.
27    return luckyNumbers.join('');
28}
29

Time and Space Complexity

The provided code calculates the k-th lucky number where lucky numbers are composed only of the digits 4 and 7.

Time Complexity

The main component of the code involves a while loop that runs until k is less than 1 << n, where n starts at 1 and gets incremented. Inside the loop, k is decremented by 1 << n. After finding the value of n such that k is within bounds, the code executes another while loop that decreases n on each iteration and constructs the lucky number. In the worst-case scenario, n will be proportional to the number of digits in the k-th lucky number.

The actual number of loop iterations is related to the bit length of the input k. Therefore, the time complexity is determined by the length of the binary representation of k, which can be described as O(log k).

The construction of the lucky number (ans.append("4") or ans.append("7")) depends on the number of digits n. Since the loops' maximum number of iterations is equal to the number of digits, the overall time complexity of constructing the lucky number is O(log k).

Space Complexity

The extra space used in the solution is allocated for the list ans to construct the return string. In the worst case, the length of ans will be equal to n, the number of digits in the k-th lucky number. Since the value of n is dependent on the logarithm of k, the space complexity is O(log k) for storing the resulting string.

The code does not use any other data structures that grow with the input size, so the overall space complexity remains O(log k).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don’t know