We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find The K-th Lucky Number

Number: 3030

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Find the k-th lucky number where a lucky number contains only the digits 4 and 7. All lucky numbers are sorted in increasing order. For example, the sequence starts as: 4, 7, 44, 47, 74, 77, 444, ... and so on.

Key Insights

  • Lucky numbers consist solely of the digits 4 and 7.
  • All lucky numbers with fewer digits are smaller than those with more digits.
  • For any given digit length L, there are 2^L lucky numbers.
  • The k-th lucky number can be found by first determining its digit length and then using a binary representation mapping (0 maps to 4 and 1 maps to 7) corresponding to its position.

Space and Time Complexity

Time Complexity: O(L) where L is the number of digits in the resulting lucky number (at most ~30). Space Complexity: O(L) for constructing the resulting string.

Solution

To obtain the k-th lucky number:

  1. Determine the minimum digit length L such that the total count of lucky numbers from lengths 1 to L is at least k.
  2. Compute the offset (zero-indexed) of k within the set of lucky numbers of length L.
  3. Convert the offset into a binary string of length L by padding with zeros.
  4. Replace each binary digit with the corresponding lucky digit ('0' becomes '4' and '1' becomes '7') to form the k-th lucky number.

Code Solutions

# Python solution for finding the k-th lucky number
def kthLuckyNumber(k):
    # Determine the digit length (L) where the k-th number falls
    length = 1
    count = 0  # cumulative count of lucky numbers with lengths less than current length
    while True:
        current_count = 2 ** length  # number of lucky numbers with this digit length
        if count + current_count >= k:
            break
        count += current_count
        length += 1

    # Compute the offset (zero-indexed) within the lucky numbers of the determined length
    offset = k - count - 1
    # Convert offset to a binary string with fixed length (padded with zeros)
    binary_str = format(offset, '0' + str(length) + 'b')
    # Map the binary digits: replace '0' with '4' and '1' with '7'
    lucky_number = ''.join('7' if ch == '1' else '4' for ch in binary_str)
    return lucky_number

# Example usage:
print(kthLuckyNumber(4))  # Expected Output: "47"
← Back to All Questions