Find The K-th Lucky Number solution and explanation
The problem
We know that 4 and 7 are lucky digits. Also, a number is called lucky if it contains only lucky digits.
You are given an integer k, return the kth lucky number represented as a string.
Example 1:
Input: k = 4 Output: "47" Explanation: The first lucky number is 4, the second one is 7, the third one is 44 and the fourth one is 47.
Example 2:
Input: k = 10 Output: "477" Explanation: Here are lucky numbers sorted in increasing order: 4, 7, 44, 47, 74, 77, 444, 447, 474, 477. So the 10th lucky number is 477.
Example 3:
Input: k = 1000 Output: "777747447" Explanation: It can be shown that the 1000th lucky number is 777747447.
Constraints:
1 <= k <= 109
Approach overview
Problem Overview: You are given an integer k. A lucky number is a number that contains only the digits 4 and 7. If all such numbers are ordered by increasing length and lexicographic order (4 before 7), return the k-th lucky number as a string.
Approach 1: Brute Force Generation (O(k log k) time, O(k) space)
The most direct idea is to generate lucky numbers in order until the k-th one appears. Start from an empty string and repeatedly append 4 and 7 to build longer numbers. A queue or BFS-style generation works well: push "4" and "7", then for each element generate current + "4" and current + "7". Each generated string represents the next lucky number in order.
This approach mirrors how binary trees expand level by level. However, you must generate all lucky numbers up to k, which means storing many intermediate strings. The total work grows with k, and each string creation costs additional time proportional to its length. Time complexity is roughly O(k log k) and space complexity is O(k). It works for small k but is unnecessary once you notice the mathematical structure.
Approach 2: Mathematical / Binary Mapping (O(log k) time, O(log k) space)
Lucky numbers follow the same pattern as binary numbers. For length n, there are exactly 2^n lucky numbers. Instead of generating them, map the index k directly to a binary representation. The key trick is to convert k + 1 to binary, then ignore the most significant bit. Every remaining bit determines a digit: 0 → 4 and 1 → 7.
Example: if k = 5, compute k + 1 = 6. Binary representation is 110. Remove the leading 1, leaving 10. Replace bits with digits (1 → 7, 0 → 4) to get 74. This directly constructs the correct lucky number without generating earlier ones.
This works because the sequence of lucky numbers corresponds exactly to binary counting if you treat 4 as 0 and 7 as 1. The extra leading bit from k + 1 naturally determines the length group (all 1-digit numbers, then 2-digit numbers, etc.). The algorithm only processes the bits of k, giving O(log k) time and O(log k) space for the resulting string.
The logic relies on properties from math, binary representation from bit manipulation, and constructing the answer as a string.
Recommended for interviews: The mathematical binary-mapping approach is what interviewers expect. The brute force generator shows you understand the ordering of lucky numbers, but the binary observation demonstrates stronger problem-solving skills and reduces the complexity from linear generation to logarithmic construction.
Solution
According to the problem description, a lucky number only contains the digits 4 and 7, so the number of n-digit lucky numbers is 2^n.
We initialize n=1, then loop to check whether k is greater than 2^n. If it is, we subtract 2^n from k and increment n, until k is less than or equal to 2^n. At this point, we just need to find the k-th lucky number among the n-digit lucky numbers.
If k is less than or equal to 2^{n-1}, then the first digit of the k-th lucky number is 4, otherwise the first digit is 7. Then we subtract 2^{n-1} from k and continue to determine the second digit, until all digits of the n-digit lucky number are determined.
The time complexity is O(log k), and the space complexity is O(log k).
class Solution:
def kthLuckyNumber(self, k: int) -> str:
n = 1
while k > 1 << n:
k -= 1 << n
n += 1
ans = []
while n:
n -= 1
if k <= 1 << n:
ans.append("4")
else:
ans.append("7")
k -= 1 << n
return "".join(ans)class Solution {
public String kthLuckyNumber(int k) {
int n = 1;
while (k > 1 << n) {
k -= 1 << n;
++n;
}
StringBuilder ans = new StringBuilder();
while (n-- > 0) {
if (k <= 1 << n) {
ans.append('4');
} else {
ans.append('7');
k -= 1 << n;
}
}
return ans.toString();
}
}class Solution {
public:
string kthLuckyNumber(int k) {
int n = 1;
while (k > 1 << n) {
k -= 1 << n;
++n;
}
string ans;
while (n--) {
if (k <= 1 << n) {
ans.push_back('4');
} else {
ans.push_back('7');
k -= 1 << n;
}
}
return ans;
}
};function kthLuckyNumber(k: number): string {
let n = 1;
while (k > 1 << n) {
k -= 1 << n;
++n;
}
const ans: string[] = [];
while (n-- > 0) {
if (k <= 1 << n) {
ans.push('4');
} else {
ans.push('7');
k -= 1 << n;
}
}
return ans.join('');
}func kthLuckyNumber(k int) string {
n := 1
for k > 1<<n {
k -= 1 << n
n++
}
ans := []byte{}
for n > 0 {
n--
if k <= 1<<n {
ans = append(ans, '4')
} else {
ans = append(ans, '7')
k -= 1 << n
}
}
return string(ans)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Generation (BFS with 4 and 7) | O(k log k) | O(k) | Useful for understanding ordering of lucky numbers or when k is very small |
| Mathematical Binary Mapping | O(log k) | O(log k) | Optimal solution; directly converts index to digits using binary representation |
Frequently asked questions
Is Find The K-th Lucky Number easy or hard?
The problem is typically rated Medium. The implementation is short, but recognizing the binary pattern behind lucky numbers requires insight into how sequence indexing relates to powers of two.
Find The K-th Lucky Number Python/Java solution
Most implementations convert k + 1 to binary and iterate through the bits to build the answer string. The same logic works in Python, Java, C++, Go, and TypeScript with time complexity O(log k).
How to solve Find The K-th Lucky Number in O(log k)?
Compute k + 1 and convert it to binary. Remove the leading bit from that binary string. Replace each remaining bit with digits where 0 becomes 4 and 1 becomes 7. The resulting string is the k-th lucky number.
What is the best approach for Find The K-th Lucky Number?
The best approach uses a mathematical mapping between lucky numbers and binary numbers. Convert k + 1 to binary, drop the most significant bit, and map 0 → 4 and 1 → 7. This directly constructs the k-th lucky number in O(log k) time without generating previous values.
Is Find The K-th Lucky Number asked at Google/Amazon/Meta?
Problems involving binary mapping, indexing sequences, and combinatorial counting frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests the ability to recognize patterns between number systems and sequences.
What data structure is used in Find The K-th Lucky Number?
The optimal solution mainly uses string construction and bit manipulation. The brute-force alternative may use a queue to generate numbers in BFS order, but the mathematical approach avoids extra data structures.
What is the time complexity of Find The K-th Lucky Number?
The optimal solution runs in O(log k) time because it processes the binary representation of k. Space complexity is also O(log k) to store the resulting string. A brute-force generation approach would take about O(k log k) time and O(k) space.