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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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) |
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) —
loading...
Last Post: Teaching Kids Programming - Find The K-th Lucky Number (Binary Mapping Pattern)
Next Post: Teaching Kids Programming - Find The K-th Lucky Number (Complete Binary Tree Algorithm)