Problem

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 thekth _ lucky number represented as a string._

Examples

Example 1:

1
2
3

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:

1
2
3
4

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:

1
2
3

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

Constraints:

  • 1 <= k <= 10^9

Solution

Method 1 – Binary Representation Mapping

Intuition

Every lucky number is made up of only ‘4’ and ‘7’. If we treat ‘4’ as 0 and ‘7’ as 1, the sequence of lucky numbers is just the sequence of binary numbers (starting from 1) mapped to ‘4’ and ‘7’. For example, the 4th lucky number is the binary 100, which is ‘47’.

Approach

  1. Convert k to its binary representation.
  2. For each bit (ignoring the first bit, since we want numbers starting from 1), map ‘0’ to ‘4’ and ‘1’ to ‘7’.
  3. Concatenate the mapped digits to form the lucky number string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    string kthLuckyNumber(int k) {
        string res;
        string bin = bitset<32>(k).to_string();
        auto it = bin.find('1');
        for (int i = it + 1; i < bin.size(); ++i) {
            res += (bin[i] == '0' ? '4' : '7');
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func kthLuckyNumber(k int) string {
    bin := strconv.FormatInt(int64(k), 2)
    res := ""
    for i := 1; i < len(bin); i++ {
        if bin[i] == '0' {
            res += "4"
        } else {
            res += "7"
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public String kthLuckyNumber(int k) {
        String bin = Integer.toBinaryString(k);
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < bin.length(); i++) {
            sb.append(bin.charAt(i) == '0' ? '4' : '7');
        }
        return sb.toString();
    }
}
1
2
3
4
5
6

class Solution {
    fun kthLuckyNumber(k: Int): String {
        val bin = Integer.toBinaryString(k)
        return bin.drop(1).map { if (it == '0') '4' else '7' }.joinToString("")
    }
}
1
2
3
4

class Solution:
    def kthLuckyNumber(self, k: int) -> str:
        b = bin(k)[2:]
        return ''.join('4' if x == '0' else '7' for x in b[1:])
1
2
3
4
5
6

impl Solution {
    pub fn kth_lucky_number(k: i32) -> String {
        let bin = format!("{:b}", k);
        bin.chars().skip(1).map(|c| if c == '0' { '4' } else { '7' }).collect()
    }
}
1
2
3
4
5
6

class Solution {
    kthLuckyNumber(k: number): string {
        const bin = k.toString(2);
        return Array.from(bin.slice(1)).map(x => x === '0' ? '4' : '7').join('');
    }
}

Complexity

  • ⏰ Time complexity: O(log k), since converting to binary and mapping is proportional to the number of bits in k.
  • 🧺 Space complexity: O(log k), for storing the binary string and result.