Jobs

Interviews

Discussions

Ugly Number II

Medium

Google

1 view

Topics:

Dynamic Programming

You are given the following problem:

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the n<sup>th</sup> ugly number.

For example:

If n = 10, the expected output is 12 because the sequence of the first 10 ugly numbers is [1, 2, 3, 4, 5, 6, 8, 9, 10, 12].
If n = 1, the expected output is 1 because 1 has no prime factors, and therefore all of its prime factors are (vacuously) limited to 2, 3, and 5.

Write a function that solves the ugly number problem, taking into account the following constraints:

1 <= n <= 1690

Explain the time and space complexity of your solution. Also, discuss a naive solution and why it would not be optimal.

Ugly Number II

Medium

Google

1 view

Topics:

Dynamic Programming

You are given the following problem:

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the n<sup>th</sup> ugly number.

For example:

If n = 10, the expected output is 12 because the sequence of the first 10 ugly numbers is [1, 2, 3, 4, 5, 6, 8, 9, 10, 12].
If n = 1, the expected output is 1 because 1 has no prime factors, and therefore all of its prime factors are (vacuously) limited to 2, 3, and 5.

Write a function that solves the ugly number problem, taking into account the following constraints:

1 <= n <= 1690

Explain the time and space complexity of your solution. Also, discuss a naive solution and why it would not be optimal.

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 value of 'n', the index of the ugly number we need to find? What is the upper bound for 'n'?
Is '1' considered an ugly number?
Should the return value be an integer, and are there any potential overflow issues given the possible magnitude of the ugly number at index 'n'?
Are we only considering the prime factors 2, 3, and 5 or could there be others?
Is n always a positive integer?

Brute Force Solution

Approach

The brute force approach to finding the nth ugly number involves systematically checking every positive number until we've found enough ugly numbers. We keep checking numbers one by one, deciding if each one is ugly or not, until we've identified the nth ugly number.

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

Start with the number 1, which is definitely an ugly number.
Next, check the number 2. Is it divisible by 2, 3, or 5? If yes, then it's an ugly number.
Continue to the next number, 3. Check if it's divisible by 2, 3, or 5. If so, it's an ugly number.
Keep checking each consecutive number (4, 5, 6, and so on).
For each number, see if it can be divided evenly by 2, 3, or 5. If it can, it's an ugly number.
Keep a running count of how many ugly numbers you've found.
Stop checking numbers when you've found the nth ugly number. That number is your answer.

Code Implementation

def find_nth_ugly_number_brute_force(n):
    ugly_number_count = 0
    current_number = 1

    while ugly_number_count < n:
        if is_ugly(current_number):
            # Increment the count if it's an ugly number
            ugly_number_count += 1

        if ugly_number_count == n:
            return current_number

        current_number += 1

def is_ugly(number):
    if number <= 0:
        return False

    # Keep dividing by 2, 3, and 5 until it is no longer divisible
    while number % 2 == 0:
        number //= 2

    while number % 3 == 0:
        number //= 3

    while number % 5 == 0:
        number //= 5

    # If the remaining number is 1, then it is an ugly number
    if number == 1:
        return True

    return False

Big(O) Analysis

Time Complexity

O(n*m) – The brute force approach iterates through numbers until n ugly numbers are found. Let 'm' represent the nth ugly number. The outer loop iterates up to 'm'. Inside the loop, a divisibility check is performed against the factors 2, 3, and 5. In the worst case, for each number up to 'm', we perform these checks. Therefore, the time complexity is O(n*m) because in the worst case 'm' is dependent on 'n', as we need 'n' ugly numbers.

Space Complexity

O(1) – The brute force approach, as described, does not utilize any significant auxiliary space. The algorithm iteratively checks each number, and only a counter is required to track the number of ugly numbers found. The space used by the counter and any temporary variables for divisibility checks is constant and independent of the input 'n' (the nth ugly number to find). Therefore, the space complexity is O(1).

Optimal Solution

Approach

To find the nth ugly number efficiently, we don't check every number. Instead, we generate ugly numbers in increasing order using the prime factors 2, 3, and 5. We maintain separate sequences of numbers multiplied by each of these primes and merge them smartly.

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

Start with the first ugly number, which is 1.
Create three 'streams' of ugly numbers by multiplying the existing ugly numbers by 2, 3, and 5, respectively.
Find the smallest number among the next available numbers from the three streams. This will be the next ugly number.
Add this new ugly number to our sequence of ugly numbers.
Advance the stream(s) that contributed to the new ugly number. If the new ugly number was produced by multiplying a previous ugly number by 2, then move to the next number in the 'times 2' stream, and so on.
Repeat the process of finding the smallest number and advancing streams until you have found the nth ugly number. Because of the way the streams are generated, the ugly numbers will always be in increasing order.

Code Implementation

def nth_ugly_number(n):
    ugly_numbers = [1]
    index_for_2 = 0
    index_for_3 = 0
    index_for_5 = 0

    while len(ugly_numbers) < n:
        # Find the next potential ugly numbers.
        next_multiple_of_2 = ugly_numbers[index_for_2] * 2
        next_multiple_of_3 = ugly_numbers[index_for_3] * 3
        next_multiple_of_5 = ugly_numbers[index_for_5] * 5

        # Choose the smallest one as the next ugly number.
        next_ugly_number = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
        ugly_numbers.append(next_ugly_number)

        # Advance the indices.
        if next_ugly_number == next_multiple_of_2:
            index_for_2 += 1

        if next_ugly_number == next_multiple_of_3:
            index_for_3 += 1

        if next_ugly_number == next_multiple_of_5:
            index_for_5 += 1

    return ugly_numbers[-1]

Big(O) Analysis

Time Complexity

O(n) – The algorithm generates n ugly numbers. For each ugly number, it performs a constant amount of work: finding the minimum of the next candidates from the three streams (2x, 3x, and 5x), adding the number to the sequence, and advancing one or more of the streams. The advancement of the streams and min heap operations takes O(1) time. Since this process repeats n times, where n is the input, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm stores the generated ugly numbers in a sequence until the nth ugly number is found. This sequence is an auxiliary data structure (typically an array or list) whose size increases linearly with N, where N is the input. Three additional index variables are used to keep track of the current position in each 'stream', but their space usage is constant. Therefore, the dominant factor in space complexity is the storage of the ugly number sequence, which requires O(N) space.

Edge Cases

Case	How to Handle
n = 0 or negative	Return 1 since the sequence starts with 1, and the 0th ugly number can be considered as 1 or throw an IllegalArgumentException.
n = 1	Return 1 as the first ugly number is 1.
Large n exceeding integer range during multiplication (integer overflow)	Use long data type to store intermediate ugly numbers to prevent integer overflow.
Extremely large n causing memory issues	Consider using a more memory-efficient data structure or algorithm, or limiting the maximum value of n.
n is close to the maximum integer value	Check if the generated ugly number exceeds the maximum integer value and handle the overflow appropriately, such as throwing an exception or returning the maximum integer value.
The same ugly number is generated by multiple factors simultaneously	The min heap or queue based approach inherently handles duplicates as it always picks the smallest available number.
The algorithm gets stuck in an infinite loop because of incorrect indices updates	Carefully manage the indices for 2, 3, and 5 multipliers to ensure progress towards generating larger ugly numbers.
Potential performance bottleneck for very large n	Optimize the min-heap implementation or explore alternative approaches like dynamic programming with memoization to improve performance.

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 value of 'n', the index of the ugly number we need to find? What is the upper bound for 'n'?
Is '1' considered an ugly number?
Should the return value be an integer, and are there any potential overflow issues given the possible magnitude of the ugly number at index 'n'?
Are we only considering the prime factors 2, 3, and 5 or could there be others?
Is n always a positive integer?

Brute Force Solution

Approach

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

Start with the number 1, which is definitely an ugly number.
Next, check the number 2. Is it divisible by 2, 3, or 5? If yes, then it's an ugly number.
Continue to the next number, 3. Check if it's divisible by 2, 3, or 5. If so, it's an ugly number.
Keep checking each consecutive number (4, 5, 6, and so on).
For each number, see if it can be divided evenly by 2, 3, or 5. If it can, it's an ugly number.
Keep a running count of how many ugly numbers you've found.
Stop checking numbers when you've found the nth ugly number. That number is your answer.

Code Implementation

def find_nth_ugly_number_brute_force(n):
    ugly_number_count = 0
    current_number = 1

    while ugly_number_count < n:
        if is_ugly(current_number):
            # Increment the count if it's an ugly number
            ugly_number_count += 1

        if ugly_number_count == n:
            return current_number

        current_number += 1

def is_ugly(number):
    if number <= 0:
        return False

    # Keep dividing by 2, 3, and 5 until it is no longer divisible
    while number % 2 == 0:
        number //= 2

    while number % 3 == 0:
        number //= 3

    while number % 5 == 0:
        number //= 5

    # If the remaining number is 1, then it is an ugly number
    if number == 1:
        return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with the first ugly number, which is 1.
Create three 'streams' of ugly numbers by multiplying the existing ugly numbers by 2, 3, and 5, respectively.
Find the smallest number among the next available numbers from the three streams. This will be the next ugly number.
Add this new ugly number to our sequence of ugly numbers.
Advance the stream(s) that contributed to the new ugly number. If the new ugly number was produced by multiplying a previous ugly number by 2, then move to the next number in the 'times 2' stream, and so on.
Repeat the process of finding the smallest number and advancing streams until you have found the nth ugly number. Because of the way the streams are generated, the ugly numbers will always be in increasing order.

Code Implementation

def nth_ugly_number(n):
    ugly_numbers = [1]
    index_for_2 = 0
    index_for_3 = 0
    index_for_5 = 0

    while len(ugly_numbers) < n:
        # Find the next potential ugly numbers.
        next_multiple_of_2 = ugly_numbers[index_for_2] * 2
        next_multiple_of_3 = ugly_numbers[index_for_3] * 3
        next_multiple_of_5 = ugly_numbers[index_for_5] * 5

        # Choose the smallest one as the next ugly number.
        next_ugly_number = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
        ugly_numbers.append(next_ugly_number)

        # Advance the indices.
        if next_ugly_number == next_multiple_of_2:
            index_for_2 += 1

        if next_ugly_number == next_multiple_of_3:
            index_for_3 += 1

        if next_ugly_number == next_multiple_of_5:
            index_for_5 += 1

    return ugly_numbers[-1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0 or negative	Return 1 since the sequence starts with 1, and the 0th ugly number can be considered as 1 or throw an IllegalArgumentException.
n = 1	Return 1 as the first ugly number is 1.
Large n exceeding integer range during multiplication (integer overflow)	Use long data type to store intermediate ugly numbers to prevent integer overflow.
Extremely large n causing memory issues	Consider using a more memory-efficient data structure or algorithm, or limiting the maximum value of n.
n is close to the maximum integer value	Check if the generated ugly number exceeds the maximum integer value and handle the overflow appropriately, such as throwing an exception or returning the maximum integer value.
The same ugly number is generated by multiple factors simultaneously	The min heap or queue based approach inherently handles duplicates as it always picks the smallest available number.
The algorithm gets stuck in an infinite loop because of incorrect indices updates	Carefully manage the indices for 2, 3, and 5 multipliers to ensure progress towards generating larger ugly numbers.
Potential performance bottleneck for very large n	Optimize the min-heap implementation or explore alternative approaches like dynamic programming with memoization to improve performance.