Skip to content

2802. Find The K-th Lucky Number πŸ”’

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

Thinking

Generating lucky numbers in order until the \(k\)-th one does not scale. There are exactly \(2^n\) lucky numbers with \(n\) digits, the same as mapping binary bits onto \(4\) and \(7\). Subtract the counts of shorter lengths to obtain \(n\), then decide each bit from the high end: write \(4\) if \(k\) lies in the first half of length \(2^{n-1}\), otherwise write \(7\) and subtract that half.

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^n\).

We initialize \(n=1\), then loop to check whether \(k\) is greater than \(2^n\). If it is, we subtract \(2^n\) from \(k\) and increment \(n\), until \(k\) is less than or equal to \(2^n\). 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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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('');
}

Comments