Find The K-th Lucky Number

Find The K-th Lucky Number

What is this problem about?

The Find The K-th Lucky Number interview question defines "lucky numbers" as integers that consist only of the digits 4 and 7. You need to find the $k^{th}$ such number in an ordered sequence: 4, 7, 44, 47, 74, 77, 444...

Why is this asked in interviews?

Amazon asks this to test a candidate's ability to map a custom number system to Binary. It evaluations whether you can recognize that a sequence with 2 options (4 and 7) is essentially a base-2 representation. It’s a test of Bit Manipulation interview patterns.

Algorithmic pattern used

This problem follows the Binary Mapping pattern.

1. Offset k: The sequence is slightly different from standard binary because lengths increase. Adding 1 to $k$ aligns it with standard binary representations where the first bit is ignored.
2. Binary Conversion: Convert $k+1$ to its binary string.
3. Mapping: Skip the first '1' of the binary string. For the remaining bits:

• '0' maps to '4'.
• '1' maps to '7'.

Example explanation

Find $k = 3$.

1. $k + 1 = 4$.
2. Binary of 4 is 100.
3. Skip the first '1': 00.
4. Map 00 to 44. Result: 44. Sequence check: 1:4, 2:7, 3:44. Correct!

Common mistakes candidates make

• Brute Force: Trying to generate lucky numbers until reaching $k$.
• Incorrect Mapping: Using standard base-2 conversion without the $+1$ offset, which makes handling different lengths difficult.
• Complexity: Over-complicating the length calculation instead of using the binary string trick.

Interview preparation tip

Whenever a problem involves a sequence made of two symbols, immediately think of Binary (Base-2). These patterns usually map directly to bit strings once you account for the offset.