Teaching Kids Programming – Find The K-th Lucky Number (Complete Binary Tree 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

Find The K-th Lucky Number (Complete Binary Tree Algorithm)

We can imagine a complete binary tree like this:

       0
    /    \
  7       8
 / \     / \
77  78  87  88

The lucky numbers in sorted order are placed (from second level) in level by level order (Breadth First Search Algorithm). The left trees are appending 7, while the right trees are appending 8. K=0 is the root, and the left kid index is:

And the right tree index is:

In other words, we can also travel from any node to its parent:

If it is left child (odd index value):

If it is right child (even index value):

So, we can travel Node K to root, appending 7 or 8 depending on if it is left or right tree until the root, And finally reverse the result:

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def kthLuckyNumber(self, k: int) -> str:
        ans = []
        while k:
            if k & 1:
                ans.append("4")
                k = (k - 1) // 2
            else:
                ans.append("7")
                k = (k - 2) // 2
        return "".join(ans[::-1])

class Solution:
    def kthLuckyNumber(self, k: int) -> str:
        ans = []
        while k:
            if k & 1:
                ans.append("4")
                k = (k - 1) // 2
            else:
                ans.append("7")
                k = (k - 2) // 2
        return "".join(ans[::-1])

The time complexity and also the space complexity is O(LogK).

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