Jobs

Interviews

Discussions

Ugly Number #1 Most Asked

Easy

GitHub

5 views

An ugly number is a positive integer which does not have a prime factor other than 2, 3, and 5.

Given an integer n, return true if n is an ugly number.

Example 1:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: n = 1
Output: true
Explanation: 1 has no prime factors.

Example 3:

Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.

Constraints:

-2³¹ <= n <= 2³¹ - 1

Try coding it in LeetCode

Ugly Number #1 Most Asked

Easy

GitHub

5 views

An ugly number is a positive integer which does not have a prime factor other than 2, 3, and 5.

Given an integer n, return true if n is an ugly number.

Example 1:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: n = 1
Output: true
Explanation: 1 has no prime factors.

Example 3:

Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.

Constraints:

-2³¹ <= n <= 2³¹ - 1

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 possible values for n? Are we concerned about integer overflow?
Is n guaranteed to be a positive integer, or should I handle the cases where n is zero or negative?
By 'ugly number', do we strictly mean a positive number whose prime factors only include 2, 3, and 5? Or are other definitions possible?
Should I return the nth ugly number in the sequence, or a boolean indicating whether n itself is an ugly number?
What is the expected behavior for very large values of 'n' in terms of computational time and memory usage?

Brute Force Solution

Approach

The brute force approach for the ugly number problem is about systematically checking numbers one by one. We start with the smallest number and keep checking if it's an ugly number until we've found enough ugly numbers.

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

Start with the number 1. We know it's an ugly number.
Check the next number, which is 2. To check if a number is ugly, we repeatedly divide it by the prime factors 2, 3, and 5 until it's no longer divisible by any of them.
If, after dividing as much as possible by 2, 3, and 5, the number becomes 1, then it's an ugly number.
If the number is not 1, it's not an ugly number.
Keep checking the next number in sequence, and repeat the division process with 2, 3, and 5. If it simplifies to one, keep it.
Continue this process, keeping track of all ugly numbers you've found.
Stop when you have found the nth ugly number. That's your answer.

Code Implementation

def find_ugly_number_brute_force(number_index):
    ugly_numbers_found = 0
    current_number = 1

    while ugly_numbers_found < number_index:
        temp_number = current_number

        # Repeatedly divide by 2, 3, and 5
        while temp_number % 2 == 0:
            temp_number //= 2

        while temp_number % 3 == 0:
            temp_number //= 3

        while temp_number % 5 == 0:
            temp_number //= 5

        # An ugly number will simplify to 1
        if temp_number == 1:
            ugly_numbers_found += 1

        current_number += 1

    # current_number was incremented one last time, we must return the number before incrementing
    return current_number - 1

Big(O) Analysis

Time Complexity

O(n*log(m)) – The algorithm iterates to find the nth ugly number. For each number checked, we repeatedly divide by 2, 3, and 5. The division process takes logarithmic time relative to the number being checked, let's call the maximum possible number checked 'm'. Thus, the number of iterations is 'n', and for each, the divisibility checks are log(m). Therefore, the overall time complexity is approximately O(n*log(m)).

Space Complexity

O(N) – The algorithm maintains a list of ugly numbers found so far. According to step 6, it keeps track of all ugly numbers until it has found the nth ugly number. Thus, the algorithm needs to store at most N ugly numbers in a list. This list constitutes auxiliary space that grows linearly with N, so the space complexity is O(N).

Optimal Solution

Approach

To find ugly numbers efficiently, we build them from the ground up using only the prime factors 2, 3, and 5. We progressively multiply existing ugly numbers by these prime factors to generate new, larger ugly numbers, ensuring we only consider numbers divisible by these primes.

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

Start with the first ugly number, which is 1.
Create three separate lists, one for multiples of 2, one for multiples of 3, and one for multiples of 5. Initially, these lists contain only 1 multiplied by 2, 3, and 5, respectively.
Find the smallest number among the three lists. This number is the next ugly number.
Add this smallest number to our list of ugly numbers.
Remove the smallest number from its respective list and replace it with the next multiple. For example, if the smallest number came from the list of multiples of 2, replace it with the next ugly number times 2.
If multiple lists contain the same smallest number, remove it from all of them and update each respective list with the next multiple of the corresponding prime.
Repeat steps 3-6 until you have found the desired number of ugly numbers.

Code Implementation

def find_ugly_number(nth_ugly_number):
    ugly_numbers = [1]
    index_for_multiple_of_2 = 0
    index_for_multiple_of_3 = 0
    index_for_multiple_of_5 = 0

    while len(ugly_numbers) < nth_ugly_number:
        next_multiple_of_2 = ugly_numbers[index_for_multiple_of_2] * 2
        next_multiple_of_3 = ugly_numbers[index_for_multiple_of_3] * 3
        next_multiple_of_5 = ugly_numbers[index_for_multiple_of_5] * 5

        # Find the minimum of the next multiples.
        next_ugly_number = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
        ugly_numbers.append(next_ugly_number)

        # Increment the indices for the multiples.
        if next_ugly_number == next_multiple_of_2:
            index_for_multiple_of_2 += 1

        if next_ugly_number == next_multiple_of_3:
            index_for_multiple_of_3 += 1

        # Avoid duplicates, so increment if equal.
        if next_ugly_number == next_multiple_of_5:
            index_for_multiple_of_5 += 1

    # Return the nth ugly number.
    return ugly_numbers[-1]

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates n times to find the first n ugly numbers. Inside the loop, we perform a constant number of operations: finding the minimum among three lists, adding the minimum to the ugly numbers list, and updating the lists of multiples. The operations within the loop do not depend on n, so the dominant factor is the single loop that runs n times. Therefore, the time complexity is O(n).

Space Complexity

O(N) – The algorithm creates three lists (multiples of 2, 3, and 5) and a list of ugly numbers. Each of these lists grows up to size N, where N is the desired number of ugly numbers. Therefore, the auxiliary space required is proportional to N, and the space complexity is O(N).

Edge Cases

Case	How to Handle
Input n is zero	Return 1, as the first ugly number is conventionally defined as 1.
Input n is negative	Throw an IllegalArgumentException, as the definition of ugly numbers does not include negative numbers.
Input n is 1	Return 1, as 1 is the first ugly number.
Large input n leading to integer overflow during calculation	Use long data type instead of int to prevent integer overflow.
Extreme case where only one prime factor is used repeatedly.	The algorithm correctly handles cases with skewed prime factor usage, like 2222...2.
Input where n is close to the maximum integer value.	Ensure array or list storing ugly numbers does not exceed available memory.
Generating a very large number of ugly numbers exceeding available memory	The algorithm must be optimized for memory efficiency, potentially using generators or limiting the size of the generated list.
Division by zero if prime factors array contains zero	Validate prime factors array for zero values, and throw exception if found.

Input n is zero

How to Handle:

Return 1, as the first ugly number is conventionally defined as 1.

Input n is negative

How to Handle:

Throw an IllegalArgumentException, as the definition of ugly numbers does not include negative numbers.

Input n is 1

How to Handle:

Return 1, as 1 is the first ugly number.

Large input n leading to integer overflow during calculation

How to Handle:

Use long data type instead of int to prevent integer overflow.

Extreme case where only one prime factor is used repeatedly.

How to Handle:

The algorithm correctly handles cases with skewed prime factor usage, like 2*2*2*2...*2.

Input where n is close to the maximum integer value.

How to Handle:

Ensure array or list storing ugly numbers does not exceed available memory.

Generating a very large number of ugly numbers exceeding available memory

How to Handle:

The algorithm must be optimized for memory efficiency, potentially using generators or limiting the size of the generated list.

Division by zero if prime factors array contains zero

How to Handle:

Validate prime factors array for zero values, and throw exception if found.

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 possible values for n? Are we concerned about integer overflow?
Is n guaranteed to be a positive integer, or should I handle the cases where n is zero or negative?
By 'ugly number', do we strictly mean a positive number whose prime factors only include 2, 3, and 5? Or are other definitions possible?
Should I return the nth ugly number in the sequence, or a boolean indicating whether n itself is an ugly number?
What is the expected behavior for very large values of 'n' in terms of computational time and memory usage?

Brute Force Solution

Approach

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

Start with the number 1. We know it's an ugly number.
Check the next number, which is 2. To check if a number is ugly, we repeatedly divide it by the prime factors 2, 3, and 5 until it's no longer divisible by any of them.
If, after dividing as much as possible by 2, 3, and 5, the number becomes 1, then it's an ugly number.
If the number is not 1, it's not an ugly number.
Keep checking the next number in sequence, and repeat the division process with 2, 3, and 5. If it simplifies to one, keep it.
Continue this process, keeping track of all ugly numbers you've found.
Stop when you have found the nth ugly number. That's your answer.

Code Implementation

def find_ugly_number_brute_force(number_index):
    ugly_numbers_found = 0
    current_number = 1

    while ugly_numbers_found < number_index:
        temp_number = current_number

        # Repeatedly divide by 2, 3, and 5
        while temp_number % 2 == 0:
            temp_number //= 2

        while temp_number % 3 == 0:
            temp_number //= 3

        while temp_number % 5 == 0:
            temp_number //= 5

        # An ugly number will simplify to 1
        if temp_number == 1:
            ugly_numbers_found += 1

        current_number += 1

    # current_number was incremented one last time, we must return the number before incrementing
    return current_number - 1

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 separate lists, one for multiples of 2, one for multiples of 3, and one for multiples of 5. Initially, these lists contain only 1 multiplied by 2, 3, and 5, respectively.
Find the smallest number among the three lists. This number is the next ugly number.
Add this smallest number to our list of ugly numbers.
Remove the smallest number from its respective list and replace it with the next multiple. For example, if the smallest number came from the list of multiples of 2, replace it with the next ugly number times 2.
If multiple lists contain the same smallest number, remove it from all of them and update each respective list with the next multiple of the corresponding prime.
Repeat steps 3-6 until you have found the desired number of ugly numbers.

Code Implementation

def find_ugly_number(nth_ugly_number):
    ugly_numbers = [1]
    index_for_multiple_of_2 = 0
    index_for_multiple_of_3 = 0
    index_for_multiple_of_5 = 0

    while len(ugly_numbers) < nth_ugly_number:
        next_multiple_of_2 = ugly_numbers[index_for_multiple_of_2] * 2
        next_multiple_of_3 = ugly_numbers[index_for_multiple_of_3] * 3
        next_multiple_of_5 = ugly_numbers[index_for_multiple_of_5] * 5

        # Find the minimum of the next multiples.
        next_ugly_number = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5)
        ugly_numbers.append(next_ugly_number)

        # Increment the indices for the multiples.
        if next_ugly_number == next_multiple_of_2:
            index_for_multiple_of_2 += 1

        if next_ugly_number == next_multiple_of_3:
            index_for_multiple_of_3 += 1

        # Avoid duplicates, so increment if equal.
        if next_ugly_number == next_multiple_of_5:
            index_for_multiple_of_5 += 1

    # Return the nth ugly number.
    return ugly_numbers[-1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is zero	Return 1, as the first ugly number is conventionally defined as 1.
Input n is negative	Throw an IllegalArgumentException, as the definition of ugly numbers does not include negative numbers.
Input n is 1	Return 1, as 1 is the first ugly number.
Large input n leading to integer overflow during calculation	Use long data type instead of int to prevent integer overflow.
Extreme case where only one prime factor is used repeatedly.	The algorithm correctly handles cases with skewed prime factor usage, like 2222...2.
Input where n is close to the maximum integer value.	Ensure array or list storing ugly numbers does not exceed available memory.
Generating a very large number of ugly numbers exceeding available memory	The algorithm must be optimized for memory efficiency, potentially using generators or limiting the size of the generated list.
Division by zero if prime factors array contains zero	Validate prime factors array for zero values, and throw exception if found.

Input n is zero

How to Handle:

Return 1, as the first ugly number is conventionally defined as 1.

Input n is negative

How to Handle:

Throw an IllegalArgumentException, as the definition of ugly numbers does not include negative numbers.

Input n is 1

How to Handle:

Return 1, as 1 is the first ugly number.

Large input n leading to integer overflow during calculation

How to Handle:

Use long data type instead of int to prevent integer overflow.

Extreme case where only one prime factor is used repeatedly.

How to Handle:

The algorithm correctly handles cases with skewed prime factor usage, like 2*2*2*2...*2.

Input where n is close to the maximum integer value.

How to Handle:

Ensure array or list storing ugly numbers does not exceed available memory.

Generating a very large number of ugly numbers exceeding available memory

How to Handle:

The algorithm must be optimized for memory efficiency, potentially using generators or limiting the size of the generated list.

Division by zero if prime factors array contains zero

How to Handle:

Validate prime factors array for zero values, and throw exception if found.

0/0 GitHub questions completed

0/0 completed