Jobs

Interviews

Discussions

Find The K-th Lucky Number

Medium

Asked by:

29 views

Topics:

Recursion

A lucky number is an integer which has a 4 or a 7 in every digit. For example, 47, 744, 4 are lucky numbers, while 5, 17, 467 are not.

Given an integer k, return the k^th smallest lucky number.

Example 1:

Input: k = 5
Output: 74
Explanation: The lucky numbers are, in sorted order: 4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777, ... The 5th lucky number is 74.

Example 2:

Input: k = 10
Output: 477

Constraints:

1 <= k <= 10⁹

Try coding it in LeetCode

Find The K-th Lucky Number

Medium

Asked by:

29 views

Topics:

Recursion

A lucky number is an integer which has a 4 or a 7 in every digit. For example, 47, 744, 4 are lucky numbers, while 5, 17, 467 are not.

Given an integer k, return the k^th smallest lucky number.

Example 1:

Input: k = 5
Output: 74
Explanation: The lucky numbers are, in sorted order: 4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777, ... The 5th lucky number is 74.

Example 2:

Input: k = 10
Output: 477

Constraints:

1 <= k <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for 'k', the index of the lucky number we are trying to find? Is 'k' 1-based or 0-based?
How are the lucky numbers defined? Is there a specific algorithm or pattern to generate them, or are they provided as input?
If 'k' is larger than the total number of lucky numbers that exist within a reasonable range, what should I return (e.g., -1, null, throw an exception)?
What data type should I use to represent the lucky numbers, considering they might grow very large (e.g., `long`, `BigInteger`)?
Can you provide a few examples of how to generate the lucky numbers and what the first few lucky numbers are, to ensure I understand the definition correctly?

Brute Force Solution

Approach

We're looking for a specific 'lucky' number in a sequence of these numbers. The brute force way is to generate all possible lucky numbers until we find the one we want. This means creating them systematically and counting until we reach the k-th one.

Here's how the algorithm would work step-by-step:

Start with the smallest possible lucky numbers, probably just the digits that make them up, such as 4 and 7.
Then, create all lucky numbers that are slightly bigger by adding 4 or 7 to the end of those smaller lucky numbers. Think of it like building them up, one digit at a time.
Keep doing this to make even bigger lucky numbers. Each time you make a new one, put it on a list.
Once you have enough lucky numbers on your list, sort them from smallest to largest.
The lucky number in the k-th position on this sorted list is your answer.

Code Implementation

def find_kth_lucky_number_brute_force(k_value):
    lucky_numbers = ['4', '7']
    
    # Keep generating lucky numbers until we have at least k numbers
    while len(lucky_numbers) < k_value:
        new_lucky_numbers = []
        for lucky_number in lucky_numbers:

            # Extend each existing number with both '4' and '7'
            new_lucky_numbers.append(lucky_number + '4')
            new_lucky_numbers.append(lucky_number + '7')

        lucky_numbers.extend(new_lucky_numbers)

    # Convert to integers and sort them in ascending order
    integer_lucky_numbers = sorted([int(number) for number in lucky_numbers])

    # Return the k-th smallest lucky number
    return integer_lucky_numbers[k_value - 1]

Big(O) Analysis

Time Complexity

O(2^k log(2^k)) – The algorithm generates lucky numbers by repeatedly appending '4' or '7' to existing lucky numbers. Since we are looking for the k-th lucky number, in the worst case, we might need to generate up to 2^k lucky numbers (as each lucky number branches into two new ones). Generating these numbers takes O(2^k) time. Sorting the generated lucky numbers (of which there can be up to 2^k) using an efficient sorting algorithm such as merge sort or quicksort would take O(2^k log(2^k)) time. Therefore, the overall time complexity is dominated by the sorting step, which is O(2^k log(2^k)).

Space Complexity

O(K) – The algorithm generates lucky numbers and stores them in a list until it contains at least K lucky numbers. This list of lucky numbers is the primary auxiliary data structure. The size of this list directly depends on K, as we need to store K lucky numbers. Once the list is filled, it's sorted, but the sorting typically happens in-place or using a small amount of extra space (depending on the sorting algorithm). Therefore, the dominant space factor is the list of K lucky numbers, leading to a space complexity of O(K).

Optimal Solution

Approach

Instead of generating all lucky numbers, which would be too slow, we will cleverly figure out which digits make up the k-th lucky number directly. We can do this by understanding the pattern of how these numbers are built.

Here's how the algorithm would work step-by-step:

Realize that lucky numbers are generated by starting with just the digits 4 and 7, and then successively appending 4 and 7 to each existing lucky number to create longer lucky numbers.
Understand that the count of lucky numbers of a certain length follows a pattern. For example, there are 2 one-digit lucky numbers, 4 two-digit lucky numbers, 8 three-digit lucky numbers, and so on.
Determine the length of the k-th lucky number. We can find this by adding up the number of lucky numbers of length 1, 2, 3, and so on, until the sum is greater than or equal to k.
Once the length is known, reduce k by the number of lucky numbers shorter than the determined length. This adjusted k now represents the position of the desired lucky number among lucky numbers of that specific length.
Now, build the lucky number digit by digit. If the adjusted k is in the first half of the range of lucky numbers of that length, the first digit is 4. Otherwise, it's 7.
Adjust k again to reflect whether the digit was 4 or 7. If it was 7, reduce k by half of the range of numbers of that length.
Repeat the process of choosing a digit (4 or 7) and adjusting k, moving from left to right. Continue until all the digits of the k-th lucky number are determined.
The final result is the k-th lucky number constructed digit by digit.

Code Implementation

def find_kth_lucky_number(k):
    lucky_number = ""
    length = 0
    numbers_of_given_length = 2

    # Determine the length of the k-th lucky number
    while k > numbers_of_given_length:
        k -= numbers_of_given_length
        length += 1
        numbers_of_given_length *= 2

    length += 1

    # Build the lucky number digit by digit
    for _ in range(length):
        numbers_of_given_length //= 2

        # If k is in the first half, the digit is 4
        if k <= numbers_of_given_length:
            lucky_number += "4"
        # Otherwise, the digit is 7
        else:
            lucky_number += "7"

            # Reduce k for next iteration
            k -= numbers_of_given_length

    return lucky_number

Big(O) Analysis

Time Complexity

O(log k) – The algorithm determines the length of the k-th lucky number by iteratively summing the number of lucky numbers of increasing lengths. This process involves at most log(k) iterations because the number of lucky numbers doubles with each length. Subsequently, building the lucky number digit by digit also takes log(k) steps, as the length of the lucky number is logarithmic in k. Therefore, the overall time complexity is dominated by these two logarithmic operations, resulting in O(log k).

Space Complexity

O(log K) – The space complexity is primarily determined by the length of the k-th lucky number, which is proportional to the number of digits it contains. The algorithm builds the lucky number digit by digit and the number of digits needed is at most log2(K), as the number of lucky numbers doubles with each additional digit. Therefore, the space needed to store the digits of the result scales with the logarithm of K, resulting in O(log K) space complexity. No other significant auxiliary data structures are used.

Edge Cases

Case	How to Handle
k <= 0	Return an appropriate error or null value since the kth lucky number is not defined for non-positive k.
k is larger than the total number of possible lucky numbers within the representable integer range.	Return an appropriate error or maximum representable lucky number if k is too large.
Integer overflow during lucky number generation.	Use appropriate data types (e.g., long) or overflow detection to prevent incorrect lucky numbers.
The algorithm is inefficient and times out for large k	Optimize the generation/search algorithm (e.g., using a heap or mathematical properties) to improve performance for larger k values.
Memory constraints prevent storing all lucky numbers for very large k	Use a generator or on-demand generation to avoid storing all lucky numbers in memory simultaneously.
The number 4 and 7 are chosen, but what if these are set dynamically?	Parameterize the 'lucky' digits 4 and 7 to be configurable to allow for different lucky number definitions.
No lucky number exists below a certain threshold; for example, if k is small but the first few lucky numbers are very large.	Handle the scenario where k is small, but all generated lucky numbers are much larger than a practical threshold, returning an error if necessary.
Algorithm enters an infinite loop because of faulty lucky number generation logic.	Implement checks to detect and break infinite loops, potentially returning an error or a maximum representable value.

k <= 0

How to Handle:

Return an appropriate error or null value since the kth lucky number is not defined for non-positive k.

k is larger than the total number of possible lucky numbers within the representable integer range.

How to Handle:

Return an appropriate error or maximum representable lucky number if k is too large.

Integer overflow during lucky number generation.

How to Handle:

Use appropriate data types (e.g., long) or overflow detection to prevent incorrect lucky numbers.

The algorithm is inefficient and times out for large k

How to Handle:

Optimize the generation/search algorithm (e.g., using a heap or mathematical properties) to improve performance for larger k values.

Memory constraints prevent storing all lucky numbers for very large k

How to Handle:

Use a generator or on-demand generation to avoid storing all lucky numbers in memory simultaneously.

The number 4 and 7 are chosen, but what if these are set dynamically?

How to Handle:

Parameterize the 'lucky' digits 4 and 7 to be configurable to allow for different lucky number definitions.

No lucky number exists below a certain threshold; for example, if k is small but the first few lucky numbers are very large.

How to Handle:

Handle the scenario where k is small, but all generated lucky numbers are much larger than a practical threshold, returning an error if necessary.

Algorithm enters an infinite loop because of faulty lucky number generation logic.

How to Handle:

Implement checks to detect and break infinite loops, potentially returning an error or a maximum representable value.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for 'k', the index of the lucky number we are trying to find? Is 'k' 1-based or 0-based?
How are the lucky numbers defined? Is there a specific algorithm or pattern to generate them, or are they provided as input?
If 'k' is larger than the total number of lucky numbers that exist within a reasonable range, what should I return (e.g., -1, null, throw an exception)?
What data type should I use to represent the lucky numbers, considering they might grow very large (e.g., `long`, `BigInteger`)?
Can you provide a few examples of how to generate the lucky numbers and what the first few lucky numbers are, to ensure I understand the definition correctly?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the smallest possible lucky numbers, probably just the digits that make them up, such as 4 and 7.
Then, create all lucky numbers that are slightly bigger by adding 4 or 7 to the end of those smaller lucky numbers. Think of it like building them up, one digit at a time.
Keep doing this to make even bigger lucky numbers. Each time you make a new one, put it on a list.
Once you have enough lucky numbers on your list, sort them from smallest to largest.
The lucky number in the k-th position on this sorted list is your answer.

Code Implementation

def find_kth_lucky_number_brute_force(k_value):
    lucky_numbers = ['4', '7']
    
    # Keep generating lucky numbers until we have at least k numbers
    while len(lucky_numbers) < k_value:
        new_lucky_numbers = []
        for lucky_number in lucky_numbers:

            # Extend each existing number with both '4' and '7'
            new_lucky_numbers.append(lucky_number + '4')
            new_lucky_numbers.append(lucky_number + '7')

        lucky_numbers.extend(new_lucky_numbers)

    # Convert to integers and sort them in ascending order
    integer_lucky_numbers = sorted([int(number) for number in lucky_numbers])

    # Return the k-th smallest lucky number
    return integer_lucky_numbers[k_value - 1]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Realize that lucky numbers are generated by starting with just the digits 4 and 7, and then successively appending 4 and 7 to each existing lucky number to create longer lucky numbers.
Understand that the count of lucky numbers of a certain length follows a pattern. For example, there are 2 one-digit lucky numbers, 4 two-digit lucky numbers, 8 three-digit lucky numbers, and so on.
Determine the length of the k-th lucky number. We can find this by adding up the number of lucky numbers of length 1, 2, 3, and so on, until the sum is greater than or equal to k.
Once the length is known, reduce k by the number of lucky numbers shorter than the determined length. This adjusted k now represents the position of the desired lucky number among lucky numbers of that specific length.
Now, build the lucky number digit by digit. If the adjusted k is in the first half of the range of lucky numbers of that length, the first digit is 4. Otherwise, it's 7.
Adjust k again to reflect whether the digit was 4 or 7. If it was 7, reduce k by half of the range of numbers of that length.
Repeat the process of choosing a digit (4 or 7) and adjusting k, moving from left to right. Continue until all the digits of the k-th lucky number are determined.
The final result is the k-th lucky number constructed digit by digit.

Code Implementation

def find_kth_lucky_number(k):
    lucky_number = ""
    length = 0
    numbers_of_given_length = 2

    # Determine the length of the k-th lucky number
    while k > numbers_of_given_length:
        k -= numbers_of_given_length
        length += 1
        numbers_of_given_length *= 2

    length += 1

    # Build the lucky number digit by digit
    for _ in range(length):
        numbers_of_given_length //= 2

        # If k is in the first half, the digit is 4
        if k <= numbers_of_given_length:
            lucky_number += "4"
        # Otherwise, the digit is 7
        else:
            lucky_number += "7"

            # Reduce k for next iteration
            k -= numbers_of_given_length

    return lucky_number

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
k <= 0	Return an appropriate error or null value since the kth lucky number is not defined for non-positive k.
k is larger than the total number of possible lucky numbers within the representable integer range.	Return an appropriate error or maximum representable lucky number if k is too large.
Integer overflow during lucky number generation.	Use appropriate data types (e.g., long) or overflow detection to prevent incorrect lucky numbers.
The algorithm is inefficient and times out for large k	Optimize the generation/search algorithm (e.g., using a heap or mathematical properties) to improve performance for larger k values.
Memory constraints prevent storing all lucky numbers for very large k	Use a generator or on-demand generation to avoid storing all lucky numbers in memory simultaneously.
The number 4 and 7 are chosen, but what if these are set dynamically?	Parameterize the 'lucky' digits 4 and 7 to be configurable to allow for different lucky number definitions.
No lucky number exists below a certain threshold; for example, if k is small but the first few lucky numbers are very large.	Handle the scenario where k is small, but all generated lucky numbers are much larger than a practical threshold, returning an error if necessary.
Algorithm enters an infinite loop because of faulty lucky number generation logic.	Implement checks to detect and break infinite loops, potentially returning an error or a maximum representable value.

k <= 0

How to Handle:

Return an appropriate error or null value since the kth lucky number is not defined for non-positive k.

k is larger than the total number of possible lucky numbers within the representable integer range.

How to Handle:

Return an appropriate error or maximum representable lucky number if k is too large.

Integer overflow during lucky number generation.

How to Handle:

Use appropriate data types (e.g., long) or overflow detection to prevent incorrect lucky numbers.

The algorithm is inefficient and times out for large k

How to Handle:

Optimize the generation/search algorithm (e.g., using a heap or mathematical properties) to improve performance for larger k values.

Memory constraints prevent storing all lucky numbers for very large k

How to Handle:

Use a generator or on-demand generation to avoid storing all lucky numbers in memory simultaneously.

The number 4 and 7 are chosen, but what if these are set dynamically?

How to Handle:

Parameterize the 'lucky' digits 4 and 7 to be configurable to allow for different lucky number definitions.

No lucky number exists below a certain threshold; for example, if k is small but the first few lucky numbers are very large.

How to Handle:

Handle the scenario where k is small, but all generated lucky numbers are much larger than a practical threshold, returning an error if necessary.

Algorithm enters an infinite loop because of faulty lucky number generation logic.

How to Handle:

Implement checks to detect and break infinite loops, potentially returning an error or a maximum representable value.