LeetCode 2802. Find The K-th Lucky Number Solution in Java, C++, Python & More | Explanation + Code

Description

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

Example 3:

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

 

Constraints:

• 1 <= k <= 109

Solutions

Solution 1: Mathematics

According to the problem description, a lucky number only contains the digits 4 and 7, so the number of n-digit lucky numbers is 2ⁿ.

We initialize n=1, then loop to check whether k is greater than 2ⁿ. If it is, we subtract 2ⁿ from k and increment n, until k is less than or equal to 2ⁿ. At this point, we just need to find the k-th lucky number among the n-digit lucky numbers.

If k is less than or equal to 2^n-1, then the first digit of the k-th lucky number is 4, otherwise the first digit is 7. Then we subtract 2^n-1 from k and continue to determine the second digit, until all digits of the n-digit lucky number are determined.

The time complexity is O(log k), and the space complexity is O(log k).

PythonJavaC++GoTypeScript

class Solution: def kthLuckyNumber(self, k: int) -> str: n = 1 while k > 1 << n: k -= 1 << n n += 1 ans = [] while n: n -= 1 if k <= 1 << n: ans.append("4") else: ans.append("7") k -= 1 << n return "".join(ans)(code-box)

class Solution { public String kthLuckyNumber(int k) { int n = 1; while (k > 1 << n) { k -= 1 << n; ++n; } StringBuilder ans = new StringBuilder(); while (n-- > 0) { if (k <= 1 << n) { ans.append('4'); } else { ans.append('7'); k -= 1 << n; } } return ans.toString(); } }(code-box)

class Solution { public: string kthLuckyNumber(int k) { int n = 1; while (k > 1 << n) { k -= 1 << n; ++n; } string ans; while (n--) { if (k <= 1 << n) { ans.push_back('4'); } else { ans.push_back('7'); k -= 1 << n; } } return ans; } };(code-box)

func kthLuckyNumber(k int) string { n := 1 for k > 1<<n { k -= 1 << n n++ } ans := []byte{} for n > 0 { n-- if k <= 1<<n { ans = append(ans, '4') } else { ans = append(ans, '7') k -= 1 << n } } return string(ans) }(code-box)

function kthLuckyNumber(k: number): string { let n = 1; while (k > 1 << n) { k -= 1 << n; ++n; } const ans: string[] = []; while (n-- > 0) { if (k <= 1 << n) { ans.push('4'); } else { ans.push('7'); k -= 1 << n; } } return ans.join(''); }(code-box)