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.
What's the relationship between a tree and a graph?
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
nto 1. Thisnvariable will eventually indicate the number of digits in our k^th^ lucky number. -
The first
whileloop checks how many digits the k^th^ lucky number will have. It works under the principle that there are2^nlucky numbers withndigits (2^n - 1possible combinations plus the all-4s combination). So, ifkis greater than2^n,kis not within the range of lucky numbers that havendigits. Therefore, we subtract2^nfromkand incrementnby 1, and iterate untilkis 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
whileloop executesntimes, decreasingnwith 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 << nis checking whetherkfits 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, andkis decremented by2^(n-1)or1 << nto reflect that we're now looking in the upper half of the range for the next digit. -
After the loop completes,
ansholds 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.
Which of these properties could exist for a graph but not a tree?
Example Walkthrough
Let's illustrate the solution approach using an example. We want to find the 5th lucky number.
-
Initialize
nto 1, because every lucky number has at least one digit. -
Begin the first
whileloop to find the number of digits our 5th lucky number will have. We know there are2^nlucky numbers for each digit length. Initially,nis 1, and2^nis 2, which is less than 5. So we incrementnto 2, and now2^nis 4, which is still less than 5. Incrementingnonce more gives us2^nas 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 = 5andn = 3. Initialize an empty listansto store the digits. -
Enter the second
whileloop, which will run three times (since our lucky number has 3 digits):- In the first iteration,
1 << nequals1 << 3which equals 8. This is greater thank(5), sokis in the lower half. We append '4' toansand do not changek. - In the second iteration, we decrement
nto 2. Now1 << nis 4, which is less thank. Hence,kis in the upper half, and we need to subtract1 << (n-1)(which is 2) fromk.kbecomes 3, and we append '7' toans. - In the third and final iteration,
nis decremented to 1, making1 << nequal to 2.kis 3, which is greater; therefore, we are again in the upper half. We subtract1 << (n-1)fromk, which is 1, makingknow equal to 2. We append '7' toans.
- In the first iteration,
-
The second
whileloop completes and our listanshas 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)
291class 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}
301#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};
361function 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}
29Which of these pictures shows the visit order of a depth-first search?
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).
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.