2802. Find The K-th Lucky Number
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. Thisn
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 are2^n
lucky numbers withn
digits (2^n - 1
possible combinations plus the all-4s combination). So, ifk
is greater than2^n
,k
is not within the range of lucky numbers that haven
digits. Therefore, we subtract2^n
fromk
and incrementn
by 1, and iterate untilk
is less than or equal to2^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 listans
, which will store each digit of the k^th^ lucky number as we compute it. -
The second
while
loop executesn
times, decreasingn
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 loopif k <= 1 << n
is checking whetherk
fits in the lower half of the range for the current digit (which would correspond to '4'). If so, '4' is appended toans
. Otherwise, '7' is appended, andk
is decremented by2^(n-1)
or1 << 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 EvaluatorExample 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 are2^n
lucky numbers for each digit length. Initially,n
is 1, and2^n
is 2, which is less than 5. So we incrementn
to 2, and now2^n
is 4, which is still less than 5. Incrementingn
once more gives us2^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
andn = 3
. Initialize an empty listans
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
equals1 << 3
which equals 8. This is greater thank
(5), sok
is in the lower half. We append '4' toans
and do not changek
. - In the second iteration, we decrement
n
to 2. Now1 << n
is 4, which is less thank
. Hence,k
is in the upper half, and we need to subtract1 << (n-1)
(which is 2) fromk
.k
becomes 3, and we append '7' toans
. - In the third and final iteration,
n
is decremented to 1, making1 << n
equal to 2.k
is 3, which is greater; therefore, we are again in the upper half. We subtract1 << (n-1)
fromk
, which is 1, makingk
now equal to 2. We append '7' toans
.
- In the first iteration,
-
The second
while
loop completes and our listans
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)
.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time