Teaching Kids Programming – Find The K-th Lucky Number (Recursive Algorithm)

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

Recursion Algorithm to Find The K-th Lucky Number

It is not difficult to find out the Recursive Formula for the N-th lucky number. For example: the 8-th lucky number is 778 which is F(3)+”8″ and the 7-th lucky number is 777 which is F(3)+”7″. Thus:

if N is odd
if N is even

With this, we can easily implement the recursion. And we can also memoize it via the @cache keyword.

class Solution:
    def kthLuckyNumber(self, k: int) -> str:
        @cache
        def f(n):
            if n == 1:
                return "4"
            if n == 2:
                return "7"
            x = f((n - 1) // 2)
            if n & 1:
                return x + "4"
            return x + "7"

        return f(k)

For each F(N), N is reduced to half, thus, the time/space complexity is O(LogN).

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