2802

2802. Find The K-th Lucky Number (Medium)

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

Hints:

• The number of lucky numbers with exactly n digits is equal to 2n.
• We can obtain how many digits the kth lucky number has.
• Imagine we know that kth lucky number has c digits. Then calculate how many numbers with c digits exist before the kth lucky number.
• Imagine the number from the previous hint is x. Now look at the binary representation of x and add some leading zero to make its length equal to c.
• Replace 0 and 1 with 4 and 7 in the number you've obtained from the previous hint.

Solution 1.

4, 7
44, 47, 74, 77
444, 447, 474, 477, 744, 747, 474, 477

Let d be the number of digits in the number, f(d) = 2 + 4 + 8 + ... = 2 * (2^d - 1) <= N

So $d = ceil(log_2(N/2 + 1))$

There are $2^d$ numbers in the level of d-digit numbers.

Let $half=2^{(d-1)}$, the index of the current number in the current level is $k - 2 * (half - 1)$. If it's less than or equal to half, then the first digit is 4, and the rest of the number has index k - half. Otherwise, it's 7 and the rest of the number has index k - 2 * half.

// OJ: https://leetcode.com/problems/find-the-k-th-lucky-number
// Author: github.com/lzl124631x
// Time: O()
// Space: O()
class Solution {
public:
    string kthLuckyNumber(int k) {
        if (k == 1) return "4";
        if (k == 2) return "7";
        int d = ceil(log(k / 2. + 1) / log(2)), half = pow(2, d - 1);
        if (k - 2 * (half - 1) <= half)  return "4" + kthLuckyNumber(k - half);
        return "7" + kthLuckyNumber(k - 2 * half);
    }
};