Teaching Kids Programming – Find The K-th Lucky Number (Binary Mapping Pattern)

Teaching Kids Programming: Videos on Data Structures and Algorithms

We know that 7 and 8 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: “78”
Explanation: The first lucky number is 7, the second one is 8, the third one is 77 and the fourth one is 78.

Example 2:
Input: k = 10
Output: “788”
Explanation: Here are lucky numbers sorted in increasing order:
7, 8, 77, 78, 87, 88, 777, 778, 787, 488. So the 10th lucky number is 788.

Example 3:
Input: k = 1000
Output: “888878778”
Explanation: It can be shown that the 1000th lucky number is 888878778.

Constraints:
1 <= k <= 10^9

Find The K-th Lucky Number (Binary Mapping Pattern)

By observing the binary string with the first lucky numbers:

When K is 1, the K+1 is 2, the binary for 2 is 10, and the lucky number is 7.
When K is 2, the K+1 is 3, the binary for 3 is 11, and the lucky number is 8.
When K is 3, the K+1 is 4, the binary for 4 is 100, and the lucky number is 77.
When K is 4, the K+1 is 5, the binary for 5 is 101, and the lucky number is 78.
When K is 5, the K+1 is 6, the binary for 6 is 110, and the lucky number is 87.
When K is 6, the K+1 is 7, the binary for 7 is 111, and the lucky number is 88.

Thus, we can map 0 to 7 and 1 to 8.

1
2
3
4

class Solution:
    def kthLuckyNumber(self, k: int) -> str:
        s = bin(k + 1)[3:]
        return s.replace("0", "7").replace("1", "8")

class Solution:
    def kthLuckyNumber(self, k: int) -> str:
        s = bin(k + 1)[3:]
        return s.replace("0", "7").replace("1", "8")

The time complexity is O(LogK) as we need to convert integer/decimal to binary. And then perform two linear search/replace which takes O(N) thus O(LogK) time. The space complexity is O(LogK) as we need to store the binary string representation of the number.

We use the bin function to convert the numbers to string. For example, bin(14) returns “0b1110” and then we use the string.replace function to replace substring “0” to “7” and “1” to “8”.

Algorithms to Find the N-th Lucky Number

• Teaching Kids Programming – Find The K-th Lucky Number (Complete Binary Tree Algorithm)
• Teaching Kids Programming – Find The K-th Lucky Number (Recursive Algorithm)
• Teaching Kids Programming – Find The K-th Lucky Number (Binary Mapping Pattern)

–EOF (The Ultimate Computing & Technology Blog) —