# 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)$.

• 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();
}
}

• 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;
}
};

• 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)


• 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)
}

• 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('');
}