LeetCode 2802 - Find The K-th Lucky Number

This problem asks us to find the k-th lucky number, where a lucky number is defined as an integer consisting only of the digits 4 and 7. For example, the sequence of lucky numbers in increasing order starts as 4, 7, 44, 47, 74, 77, 444, and so on.

leetcodemediummathstringbit-manipulation

LeetCode Problem 2802

Difficulty: 🟡 Medium
Topics: Math, String, Bit Manipulation

Solution

Problem Understanding

This problem asks us to find the k-th lucky number, where a lucky number is defined as an integer consisting only of the digits 4 and 7. For example, the sequence of lucky numbers in increasing order starts as 4, 7, 44, 47, 74, 77, 444, and so on.

The input is a single integer k (1 ≤ k ≤ 10^9), which specifies the position in the sorted list of lucky numbers. The output should be the lucky number at that position, represented as a string. Using a string is important because the numbers can become very large and exceed typical integer ranges.

Key points in understanding the problem include:

  • Lucky numbers are strictly composed of the digits 4 and 7.
  • Numbers are considered in increasing order as if sorted lexicographically by numeric value.
  • The input k can be as large as 10^9, meaning generating all numbers sequentially would be infeasible.
  • Edge cases include k = 1 (smallest lucky number) and very large k (requiring many digits).

The problem guarantees k is always valid, so we do not need to handle negative numbers or zero. However, we need a method that scales efficiently to large values of k.

Approaches

Brute Force

A naive approach would generate lucky numbers in order until we reach the k-th one. This could be done using recursion or a queue. For example, starting with "4" and "7", we could append "4" and "7" repeatedly to generate longer lucky numbers and track the sequence.

While this method is correct, it is far too slow for k up to 10^9. Generating numbers sequentially would require keeping track of all previous numbers, leading to exponential time and memory usage.

Optimal Insight

The key insight is that lucky numbers can be represented as binary numbers, with '4' corresponding to 0 and '7' corresponding to 1. For instance, the sequence of lucky numbers is analogous to counting in binary:

1-digit: 4 (0), 7 (1)
2-digit: 44 (00), 47 (01), 74 (10), 77 (11)
3-digit: 444 (000), 447 (001), 474 (010), ...

Using this observation, the problem reduces to:

  1. Determine how many digits the k-th number has.
  2. Represent k as a binary number within that digit length.
  3. Map 0 → 4 and 1 → 7 to form the lucky number.

This method is efficient because it avoids generating all previous lucky numbers and directly constructs the answer.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^d) where d = number of digits needed O(2^d) Generates all lucky numbers until k-th; infeasible for k ~ 10^9
Optimal O(log k) O(log k) Converts k to binary-like representation to construct the lucky number directly

Algorithm Walkthrough

  1. Initialize a variable length = 1. This will represent the number of digits in the lucky number we are trying to construct.
  2. Compute the total number of lucky numbers with length digits using the formula 2^length.
  3. While k is greater than the count of numbers with the current length, subtract that count from k and increment length. This identifies the correct number of digits for the k-th lucky number.
  4. Once the correct length is determined, treat k-1 as a zero-based index.
  5. Convert k-1 into a binary string of length length. Each bit represents whether to choose 4 (bit = 0) or 7 (bit = 1).
  6. Map each bit to the corresponding lucky digit and concatenate them to form the resulting string.
  7. Return the resulting string as the k-th lucky number.

Why it works: Every lucky number corresponds uniquely to a binary number where 0 → 4 and 1 → 7. By adjusting k to the right digit length, we ensure that the binary mapping correctly indexes into the sorted sequence of lucky numbers.

Python Solution

class Solution:
    def kthLuckyNumber(self, k: int) -> str:
        length = 1
        count = 2 ** length
        
        while k > count:
            k -= count
            length += 1
            count = 2 ** length
        
        k -= 1  # zero-based index
        binary_repr = bin(k)[2:].zfill(length)
        result = ''.join('4' if c == '0' else '7' for c in binary_repr)
        return result

This Python implementation first determines the number of digits required by subtracting the total number of lucky numbers with fewer digits. Then, it converts the zero-based index k-1 to binary, pads it to the correct length, and maps 0 → 4, 1 → 7 to produce the lucky number string.

Go Solution

import (
    "strconv"
    "strings"
)

func kthLuckyNumber(k int) string {
    length := 1
    count := 1 << length // 2^length
    
    for k > count {
        k -= count
        length++
        count = 1 << length
    }
    
    k -= 1 // zero-based index
    binaryStr := strconv.FormatInt(int64(k), 2)
    for len(binaryStr) < length {
        binaryStr = "0" + binaryStr
    }
    
    var sb strings.Builder
    for _, ch := range binaryStr {
        if ch == '0' {
            sb.WriteByte('4')
        } else {
            sb.WriteByte('7')
        }
    }
    return sb.String()
}

In Go, we handle integer arithmetic explicitly with bit shifts and use strings.Builder for efficient string concatenation. Padding the binary string ensures it has the correct number of digits before mapping to lucky digits.

Worked Examples

Example 1: k = 4

  1. length = 1, count = 2 → k > 2, so k = 4 - 2 = 2, length = 2
  2. count = 4 → k <= 4, stop
  3. k-1 = 1 → binary "01"
  4. Map "0" → 4, "1" → 7 → result "47"

Example 2: k = 10

  1. length = 1, count = 2 → k > 2, k = 8, length = 2
  2. count = 4 → k > 4, k = 4, length = 3
  3. count = 8 → k <= 8, stop
  4. k-1 = 3 → binary "011"
  5. Map to lucky digits → 4 7 7 → result "477"

Example 3: k = 1000

  1. Iterate lengths and subtract counts until length = 10, k = some value
  2. Convert k-1 to binary string of length 10
  3. Map 0 → 4, 1 → 7 → result "777747447"

Complexity Analysis

Measure Complexity Explanation
Time O(log k) Each subtraction reduces k exponentially; converting k to binary and mapping digits is O(log k)
Space O(log k) Space for binary string and result string of length proportional to log k

The complexity is efficient because the number of digits in the k-th lucky number grows logarithmically with k. Memory usage is minimal, proportional to the number of digits.

Test Cases

# Provided examples
assert Solution().kthLuckyNumber(4) == "47"  # basic 2-digit number
assert Solution().kthLuckyNumber(10) == "477"  # 3-digit number
assert Solution().kthLuckyNumber(1000) == "777747447"  # large k

# Edge and boundary cases
assert Solution().kthLuckyNumber(1) == "4"  # smallest lucky number
assert Solution().kthLuckyNumber(2) == "7"  # second smallest
assert Solution().kthLuckyNumber(3) == "44"  # first 2-digit lucky number
assert Solution().kthLuckyNumber(15) == "777"  # last 3-digit lucky number
Test Why
k=4 Checks small 2-digit lucky number
k=10 Verifies correct 3-digit construction
k=1000 Stress test for large k
k=1,2,3 Checks smallest numbers and first 2-digit number
k=15 Ensures last number of a digit length is correct

Edge Cases

Edge Case 1: k = 1

This tests the very first lucky number. A naive implementation might subtract counts incorrectly or fail to handle the zero-based index adjustment. The algorithm correctly returns "4".

Edge Case 2: k at boundary of digit length

For example, k = 2^d + 1, which is the first number of the next digit length. Subtracting previous counts ensures that we correctly identify the new length and do not misalign the binary mapping.

Edge Case