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