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.

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.

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:

1. Initially k = 5, n = 1
2. Check: 5 > 2^1 = 2? Yes, so k = 5 - 2 = 3, n = 2
3. Check: 3 > 2^2 = 4? No, so we stop. The number has 2 digits.
4. 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
5. 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

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).

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.