Find The K-th Lucky Number - Video Solutions

Problem Overview: You are given an integer k. A lucky number is a number that contains only the digits 4 and 7. If all such numbers are ordered by increasing length and lexicographic order (4 before 7), return the k-th lucky number as a string.

Approach 1: Brute Force Generation (O(k log k) time, O(k) space)

The most direct idea is to generate lucky numbers in order until the k-th one appears. Start from an empty string and repeatedly append 4 and 7 to build longer numbers. A queue or BFS-style generation works well: push "4" and "7", then for each element generate current + "4" and current + "7". Each generated string represents the next lucky number in order.

This approach mirrors how binary trees expand level by level. However, you must generate all lucky numbers up to k, which means storing many intermediate strings. The total work grows with k, and each string creation costs additional time proportional to its length. Time complexity is roughly O(k log k) and space complexity is O(k). It works for small k but is unnecessary once you notice the mathematical structure.

Approach 2: Mathematical / Binary Mapping (O(log k) time, O(log k) space)

Lucky numbers follow the same pattern as binary numbers. For length n, there are exactly 2^n lucky numbers. Instead of generating them, map the index k directly to a binary representation. The key trick is to convert k + 1 to binary, then ignore the most significant bit. Every remaining bit determines a digit: 0 → 4 and 1 → 7.

Example: if k = 5, compute k + 1 = 6. Binary representation is 110. Remove the leading 1, leaving 10. Replace bits with digits (1 → 7, 0 → 4) to get 74. This directly constructs the correct lucky number without generating earlier ones.

This works because the sequence of lucky numbers corresponds exactly to binary counting if you treat 4 as 0 and 7 as 1. The extra leading bit from k + 1 naturally determines the length group (all 1-digit numbers, then 2-digit numbers, etc.). The algorithm only processes the bits of k, giving O(log k) time and O(log k) space for the resulting string.

The logic relies on properties from math, binary representation from bit manipulation, and constructing the answer as a string.

Recommended for interviews: The mathematical binary-mapping approach is what interviewers expect. The brute force generator shows you understand the ordering of lucky numbers, but the binary observation demonstrates stronger problem-solving skills and reduces the complexity from linear generation to logarithmic construction.