2802. Find The K-th Lucky Number

MediumBit ManipulationMathString

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

In this problem, we define lucky digits as the digits 4 and 7. A lucky number is a number that contains only these lucky digits.

For example:

4, 7, 44, 47, 74, 77 are lucky numbers (they only contain digits 4 and 7)
14, 457, 8 are not lucky numbers (they contain other digits besides 4 and 7)

When we list all lucky numbers in ascending order, we get the sequence: 4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777, ...

Given an integer k, you need to find the k-th lucky number in this sequence and return it as a string.

For instance:

If k = 1, the answer is "4" (the 1st lucky number)
If k = 2, the answer is "7" (the 2nd lucky number)
If k = 3, the answer is "44" (the 3rd lucky number)
If k = 4, the answer is "47" (the 4th lucky number)

The key insight is that there are exactly 2^n lucky numbers with n digits (since each digit position can be either 4 or 7). The solution uses this property to first determine how many digits the k-th lucky number has, then constructs it digit by digit using binary-like logic where 4 represents 0 and 7 represents 1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

Lucky numbers correspond to binary representations of k mapped onto digits 4 and 7.

Open in Flowchart

Intuition

Let's think about how lucky numbers are structured. Since each digit can only be 4 or 7, we have exactly 2 choices for each position. This creates a pattern:

1-digit lucky numbers: 4, 7 → 2 numbers total
2-digit lucky numbers: 44, 47, 74, 77 → 4 numbers total
3-digit lucky numbers: 444, 447, 474, 477, 744, 747, 774, 777 → 8 numbers total

We can see that there are 2^n lucky numbers with exactly n digits.

To find the k-th lucky number, we first need to figure out how many digits it has. We keep accumulating the counts: if k ≤ 2, it's a 1-digit number; if k ≤ 2 + 4 = 6, it's a 2-digit number; if k ≤ 2 + 4 + 8 = 14, it's a 3-digit number, and so on.

Once we know the number of digits n, we need to find which of the 2^n possible n-digit lucky numbers is our answer. Here's where the binary analogy becomes useful: we can think of lucky numbers as binary numbers where 4 represents 0 and 7 represents 1.

For example, among 3-digit lucky numbers:

The 1st one (444) corresponds to binary 000
The 2nd one (447) corresponds to binary 001
The 3rd one (474) corresponds to binary 010
The 4th one (477) corresponds to binary 011
And so on...

To construct the actual number digit by digit, we use a clever observation: for the leftmost digit, if our position k is in the first half (≤ 2^(n-1)), we use 4; otherwise, we use 7. Then we adjust k accordingly and repeat for the next digit. This is essentially converting the position k into its binary representation and mapping 0→4 and 1→7.

Pattern Learn more about Math patterns.

Solution Approach

The implementation follows two main steps: finding the number of digits, then constructing the lucky number digit by digit.

Step 1: Determine the number of digits

We start with n = 1 and iterate while k > 2^n. In each iteration:

If k > 2^n, we subtract 2^n from k (removing all n-digit lucky numbers from consideration)
Increment n to check the next digit length
Continue until k ≤ 2^n

This tells us that the k-th lucky number has n digits, and it's the adjusted k-th number among all n-digit lucky numbers.

Step 2: Construct the lucky number digit by digit

Now we build the n-digit lucky number from left to right. For each position:

Decrement n by 1 (moving to the next digit position)
Check if k ≤ 2^(n-1):
- If yes, the current digit is 4 (we're in the first half)
- If no, the current digit is 7 (we're in the second half), and we subtract 2^(n-1) from k
Continue until all n digits are determined

The bit shift operation 1 << n is used as an efficient way to calculate 2^n.

Example walkthrough for k = 5:

Initially k = 5, n = 1
Check: 5 > 2^1 = 2? Yes, so k = 5 - 2 = 3, n = 2
Check: 3 > 2^2 = 4? No, so we stop. The number has 2 digits.
Build the number:
- First digit: 3 ≤ 2^1 = 2? No, so digit is 7, k = 3 - 2 = 1
- Second digit: 1 ≤ 2^0 = 1? Yes, so digit is 4
Result: "74"

This approach efficiently finds the k-th lucky number in O(log k) time complexity, as we only need to process at most log₂(k) digits.

Example Walkthrough

Let's walk through finding the 6th lucky number (k = 6).

Step 1: Determine the number of digits

Starting with k = 6, n = 1:

Is 6 > 2^1 = 2? Yes, so we have more than 1 digit
Subtract: k = 6 - 2 = 4, increment n = 2
Is 4 > 2^2 = 4? No, so we stop

The 6th lucky number has 2 digits and is the 4th among all 2-digit lucky numbers.

Step 2: Construct the lucky number digit by digit

Now we build the 2-digit number with k = 4, n = 2:

First digit (leftmost):

Decrement n: n = 2 - 1 = 1
Is k ≤ 2^(n-1) = 2^0 = 1?
Is 4 ≤ 1? No, so the first digit is 7
Update k: k = 4 - 1 = 3

Wait, let me recalculate this more carefully:

First digit:

We have n = 2 digits to place, currently at position k = 4
For the first digit: check if k ≤ 2^(n-1) = 2^1 = 2
Is 4 ≤ 2? No, so first digit is 7
Update: k = 4 - 2 = 2, n = 1

Second digit:

We have n = 1 digit left, k = 2
Check if k ≤ 2^(n-1) = 2^0 = 1
Is 2 ≤ 1? No, so second digit is 7

Result: "77"

Let's verify by listing: 4 (1st), 7 (2nd), 44 (3rd), 47 (4th), 74 (5th), 77 (6th) ✓

The algorithm correctly identifies that we need a 2-digit number and builds it by making binary-like decisions at each position, mapping to digits 4 and 7.

Solution Implementation

1class Solution:
2    def kthLuckyNumber(self, k: int) -> str:
3        # Lucky numbers form a complete binary tree pattern:
4        # Level 1: 4, 7 (2^1 = 2 numbers)
5        # Level 2: 44, 47, 74, 77 (2^2 = 4 numbers)
6        # Level 3: 444, 447, 474, 477, 744, 747, 774, 777 (2^3 = 8 numbers)
7
8        # Find the level (number of digits) of the k-th lucky number
9        level = 1
10        while k > (1 << level):  # While k > 2^level
11            k -= (1 << level)  # Subtract numbers from previous levels
12            level += 1
13
14        # Build the lucky number digit by digit
15        result = []
16
17        # For each position in the number (from left to right)
18        while level > 0:
19            level -= 1
20
21            # Check if k is in the left half or right half of current subtree
22            if k <= (1 << level):  # If k <= 2^level, choose left branch
23                result.append("4")  # Left branch uses digit 4
24            else:
25                result.append("7")  # Right branch uses digit 7
26                k -= (1 << level)  # Adjust k for right subtree
27
28        return "".join(result)
29

1class Solution {
2    public String kthLuckyNumber(int k) {
3        // Find the length of the k-th lucky number
4        // Lucky numbers form a complete binary tree where each level has 2^n numbers
5        int length = 1;
6        while (k > (1 << length)) {  // While k is greater than 2^length
7            k -= (1 << length);      // Subtract the count of numbers in this level
8            length++;                 // Move to the next level (longer numbers)
9        }
10
11        // Build the lucky number digit by digit
12        StringBuilder result = new StringBuilder();
13
14        // For each position in the number (from left to right)
15        while (length-- > 0) {
16            // Check if k is in the left half or right half of remaining possibilities
17            if (k <= (1 << length)) {     // If k is in the left half (positions 1 to 2^length)
18                result.append('4');        // Append '4' for left branch
19            } else {                       // If k is in the right half
20                result.append('7');        // Append '7' for right branch
21                k -= (1 << length);        // Adjust k to be relative to the right subtree
22            }
23        }
24
25        return result.toString();
26    }
27}
28

1class Solution {
2public:
3    string kthLuckyNumber(int k) {
4        // Find the length of the k-th lucky number
5        // Lucky numbers of length n have 2^n possibilities
6        int length = 1;
7        while (k > (1 << length)) {
8            k -= (1 << length);  // Subtract count of numbers with current length
9            ++length;            // Move to next length
10        }
11
12        // Build the lucky number digit by digit
13        string result;
14        while (length--) {
15            // Check if k is in the left half (positions 1 to 2^(length-1))
16            if (k <= (1 << length)) {
17                result.push_back('4');  // Choose '4' for left subtree
18            } else {
19                result.push_back('7');  // Choose '7' for right subtree
20                k -= (1 << length);     // Adjust k for right subtree
21            }
22        }
23
24        return result;
25    }
26};
27

1/**
2 * Finds the k-th lucky number in the sequence where lucky numbers
3 * only contain digits 4 and 7.
4 *
5 * The lucky numbers are ordered as: 4, 7, 44, 47, 74, 77, 444, 447, ...
6 * They form a complete binary tree pattern where 4 represents left (0)
7 * and 7 represents right (1).
8 *
9 * @param k - The position of the lucky number to find (1-indexed)
10 * @returns The k-th lucky number as a string
11 */
12function kthLuckyNumber(k: number): string {
13    // Find the length of the k-th lucky number
14    // Numbers of each length form groups: 2^1, 2^2, 2^3, ...
15    let length: number = 1;
16    while (k > (1 << length)) {
17        // Subtract the count of lucky numbers with current length
18        k -= (1 << length);
19        length++;
20    }
21
22    // Build the lucky number digit by digit
23    const result: string[] = [];
24
25    // Construct the number from left to right using binary representation
26    // k now represents the position within numbers of the target length
27    while (length > 0) {
28        length--;
29
30        // Check if k is in the left half of remaining positions
31        if (k <= (1 << length)) {
32            // Left half: append '4'
33            result.push('4');
34        } else {
35            // Right half: append '7'
36            result.push('7');
37            // Adjust k to be relative to the right subtree
38            k -= (1 << length);
39        }
40    }
41
42    return result.join('');
43}
44

Time and Space Complexity

The time complexity is O(log k) and the space complexity is O(log k).

Time Complexity Analysis:

The first while loop runs while k > 1 << n, which means k > 2^n. This loop increments n until 2^n ≥ k, so it runs approximately log₂(k) times.
The second while loop runs exactly n times, where n ≈ log₂(k) from the first loop.
Inside the second loop, all operations (comparison, append, subtraction) are O(1).
Therefore, the overall time complexity is O(log k) + O(log k) = O(log k).

Space Complexity Analysis:

The variable ans is a list that stores the digits of the result.
In each iteration of the second while loop, we append one character to ans.
The second loop runs n times where n ≈ log₂(k).
The final string created by "".join(ans) also has length proportional to log k.
Therefore, the space complexity is O(log k).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Level Calculation

The Pitfall: A common mistake is incorrectly handling the boundary when determining which level (number of digits) the k-th lucky number belongs to. Developers might use k >= (1 << level) instead of k > (1 << level) in the while loop condition, or forget to adjust k properly after each level.

Why it happens: The confusion arises because there are exactly 2^n numbers at level n, and when k equals 2^n, it should be the last number of that level, not the first number of the next level.

Example of incorrect code:

# INCORRECT: Using >= instead of >
level = 1
while k >= (1 << level):  # Wrong condition!
    k -= (1 << level)
    level += 1

Impact: This would cause k=2 to incorrectly map to "44" instead of "7", and k=6 to map to "444" instead of "77".

Solution: Always use strict inequality k > (1 << level) to ensure that when k equals exactly 2^level, it stays in the current level as the last number.

2. Incorrect Binary Mapping Logic

The Pitfall: Another frequent error is reversing the digit mapping logic or incorrectly adjusting k when choosing the right branch (digit 7).

Example of incorrect code:

# INCORRECT: Forgetting to adjust k for right branch
while level > 0:
    level -= 1
    if k <= (1 << level):
        result.append("4")
    else:
        result.append("7")
        # Missing: k -= (1 << level)  # Forgot this line!

Impact: Without adjusting k after choosing the right branch, subsequent digits will be calculated incorrectly. For example, k=4 would produce "77" instead of "47".

Solution: Always remember to subtract 2^level from k when choosing the right branch (digit 7), as this represents moving to the right half of the remaining search space.

3. Using 0-based vs 1-based Indexing

The Pitfall: Mixing up whether the problem asks for 0-indexed or 1-indexed k-th number. Some might assume k=0 refers to the first lucky number.

Impact: If the code assumes 0-based indexing when the problem expects 1-based (or vice versa), all results will be shifted by one position.

Solution: Carefully read the problem statement. In this case, k=1 refers to the first lucky number "4", indicating 1-based indexing. If your implementation uses 0-based logic internally, remember to adjust at the beginning or end accordingly.

Ready to land your dream job?

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

Start Evaluator

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