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.

Description Hints 5 Solution Video 7:55

2802. Find The K-th Lucky Number

Medium76.1% acceptancePremium elsewhere, free here

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 k^th 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 10^th lucky number is 477.

Example 3:

Input: k = 1000
Output: "777747447"
Explanation: It can be shown that the 1000^th lucky number is 777747447.

Constraints:

1 <= k <= 10⁹

Topics

Hints open one at a time

Hint 1

The number of lucky numbers with exactly n digits is equal to 2ⁿ.

Hint 2

We can obtain how many digits the k^th lucky number has.

Hint 3

Imagine we know that k^th lucky number has c digits. Then calculate how many numbers with c digits exist before the k^th lucky number.

Hint 4

Imagine the number from the previous hint is x. Now look at the binary representation of x and add some leading zero to make its length equal to c.

Hint 5

Replace 0 and 1 with 4 and 7 in the number you've obtained from the previous hint.

7:55

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

Your code is saved on this device.Solution