Jobs

Interviews

Discussions

Super Ugly Number

Medium

Asked by:

37 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the n^th super ugly number.

The n^th super ugly number is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

Example 2:

Input: n = 1, primes = [2,3,5]
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

Constraints:

1 <= n <= 10⁵
1 <= primes.length <= 100
2 <= primes[i] <= 1000
primes[i] is guaranteed to be a prime number.
All the values of primes are unique and sorted in ascending order.

Try coding it in LeetCode

Super Ugly Number

Medium

Asked by:

37 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the n^th super ugly number.

The n^th super ugly number is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

Example 2:

Input: n = 1, primes = [2,3,5]
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

Constraints:

1 <= n <= 10⁵
1 <= primes.length <= 100
2 <= primes[i] <= 1000
primes[i] is guaranteed to be a prime number.
All the values of primes are unique and sorted in ascending order.

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 expected range for `n`, the index of the super ugly number to be returned?
What is the expected range and data type (integer, float) for the prime numbers in the `primes` array? Can I assume they are all positive integers?
Can the `primes` array be empty or contain duplicate values?
What should the function return if `n` is less than or equal to 0?
Is the `primes` array guaranteed to be sorted in ascending order?

Brute Force Solution

Approach

To find super ugly numbers using brute force, we essentially try generating every possible number that could be one. We keep generating numbers and checking if they fit our definition of a super ugly number, discarding the ones that don't.

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

Start with the number 1, which is always the first super ugly number.
Generate new numbers by multiplying existing super ugly numbers with the prime numbers provided.
Check if each newly generated number is a multiple of only the given prime numbers.
If it is, and if it's also bigger than the largest super ugly number we already have, then it's potentially a new super ugly number.
Maintain a collection of all the potential super ugly numbers and from this collection choose the smallest one as the next super ugly number.
Repeat the process of generating, checking, and selecting the next super ugly number until you have found the required number of super ugly numbers.

Code Implementation

def super_ugly_number_brute_force(number_of_ugly_numbers, primes):
    super_ugly_numbers = [1]

    while len(super_ugly_numbers) < number_of_ugly_numbers:
        potential_ugly_numbers = []
        for ugly_number in super_ugly_numbers:
            for prime_number in primes:
                new_number = ugly_number * prime_number

                # We add a new number to the pool
                potential_ugly_numbers.append(new_number)

        next_ugly_number = min(potential_ugly_numbers)

        # Check if the number is actually super ugly
        is_super_ugly = True
        temp_number = next_ugly_number
        for prime_number in primes:
            while temp_number % prime_number == 0:
                temp_number //= prime_number

        if temp_number != 1:
            is_super_ugly = False

        # Append only if it is truly super ugly
        if is_super_ugly and next_ugly_number > super_ugly_numbers[-1]:
            super_ugly_numbers.append(next_ugly_number)

        #Eliminate duplicates after adding a new super ugly number
        super_ugly_numbers = sorted(list(set(super_ugly_numbers)))

        #If we exceeded the number needed we exit the loop
        if len(super_ugly_numbers) >= number_of_ugly_numbers:
            break

    return super_ugly_numbers[number_of_ugly_numbers - 1]

Big(O) Analysis

Time Complexity

O(k*n*m) – The brute force approach iterates to find 'n' super ugly numbers. In each iteration, it generates potential candidates by multiplying existing super ugly numbers with given prime numbers. Assuming there are at most 'k' candidate numbers at any given time in the candidate collection, finding the minimum from these candidates takes O(k). For each of the n super ugly number calculations, primality check is done by performing divisions on the candidate with each prime number. If there are m prime numbers then it takes O(m) time to check primality for each candidate. Thus, each of the 'n' iterations roughly does the following: minimum finding takes O(k) and primality check takes O(m). Combining them makes the time complexity O(k*n*m).

Space Complexity

O(N) – The algorithm maintains a collection of potential super ugly numbers as described in steps 4 and 5. This collection can grow up to the size of N, where N is the number of super ugly numbers we need to find. Therefore, an auxiliary data structure (effectively a list or set) of size N is created to store these potential candidates. Consequently, the auxiliary space complexity is O(N).

Optimal Solution

Approach

Instead of exhaustively checking every single number, we build the sequence of Super Ugly Numbers from the ground up. We keep track of the next potential multiple of each prime factor, always selecting the smallest one to extend our sequence and advancing the corresponding prime factor's multiple.

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

Start with the first Super Ugly Number, which is always 1.
For each prime number given, keep track of what multiple of that prime could be the next Super Ugly Number.
Find the smallest of all these potential next Super Ugly Numbers. This is the next number in our sequence.
Add this number to our sequence of Super Ugly Numbers.
For any prime whose multiple matched the new Super Ugly Number, calculate the next multiple of that prime by multiplying it with a Super Ugly Number in the sequence.
Repeat steps 3-5 until you have found the required number of Super Ugly Numbers.

Code Implementation

def super_ugly_number(number, primes):
    ugly_numbers = [1]
    prime_indices = [0] * len(primes)

    for _ in range(1, number):
        next_ugly_numbers = [primes[i] * ugly_numbers[prime_indices[i]] for i in range(len(primes))]

        # Find the minimum potential ugly number.
        next_ugly = min(next_ugly_numbers)
        ugly_numbers.append(next_ugly)

        # Advance prime indices for multiples == min.
        for i in range(len(primes)):

            if next_ugly_numbers[i] == next_ugly:
                prime_indices[i] += 1

    return ugly_numbers[-1]

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates n times to find the nth Super Ugly Number. Inside the loop, it iterates through the k primes to find the minimum next Super Ugly Number. Updating the indices for primes also takes O(k) time in the worst case, since there can be multiple primes whose multiples equal the newly found Super Ugly Number. Therefore, the overall time complexity is O(n*k), where n is the desired number of Super Ugly Numbers and k is the number of prime factors given as input.

Space Complexity

O(N) – The algorithm stores the generated Super Ugly Numbers in a sequence, which grows until it contains N numbers. This sequence constitutes the dominant auxiliary space used. Other variables such as those keeping track of the multiples of the prime numbers and their indices occupy constant space. Therefore, the auxiliary space complexity is determined by the space required to store the sequence of N Super Ugly Numbers.

Edge Cases

Case	How to Handle
Empty primes array	If primes is empty, return an empty list or a list containing only 1, depending on problem requirements.
n is 0 or negative	If n is 0, return an empty list; if n is negative, throw an IllegalArgumentException or return an empty list, as super ugly numbers are not defined for non-positive n.
n is 1	Return a list containing only 1 since the first super ugly number is always 1.
primes array contains duplicates	The algorithm should still work correctly as duplicates won't affect the generation of super ugly numbers if the algorithm already avoids using the same index twice.
primes array contains 1	The algorithm should handle this correctly; if 1 is in primes, the loop will iterate on 1, multiplying by 1 repeatedly but not adding to the result if already present.
Integer overflow when multiplying prime numbers	Use long data type to prevent integer overflow during multiplication of existing super ugly numbers and prime numbers.
Large n value causing memory issues	The algorithm can be optimized with generators in languages like Python or lazy evaluation to minimize memory usage for very large n.
primes array contains very large prime numbers	Using long data type will handle them, however execution time can be affected by repeated large number multiplications.

Empty primes array

How to Handle:

If primes is empty, return an empty list or a list containing only 1, depending on problem requirements.

n is 0 or negative

How to Handle:

If n is 0, return an empty list; if n is negative, throw an IllegalArgumentException or return an empty list, as super ugly numbers are not defined for non-positive n.

n is 1

How to Handle:

Return a list containing only 1 since the first super ugly number is always 1.

primes array contains duplicates

How to Handle:

The algorithm should still work correctly as duplicates won't affect the generation of super ugly numbers if the algorithm already avoids using the same index twice.

primes array contains 1

How to Handle:

The algorithm should handle this correctly; if 1 is in primes, the loop will iterate on 1, multiplying by 1 repeatedly but not adding to the result if already present.

Integer overflow when multiplying prime numbers

How to Handle:

Use long data type to prevent integer overflow during multiplication of existing super ugly numbers and prime numbers.

Large n value causing memory issues

How to Handle:

The algorithm can be optimized with generators in languages like Python or lazy evaluation to minimize memory usage for very large n.

primes array contains very large prime numbers

How to Handle:

Using long data type will handle them, however execution time can be affected by repeated large number multiplications.

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 expected range for `n`, the index of the super ugly number to be returned?
What is the expected range and data type (integer, float) for the prime numbers in the `primes` array? Can I assume they are all positive integers?
Can the `primes` array be empty or contain duplicate values?
What should the function return if `n` is less than or equal to 0?
Is the `primes` array guaranteed to be sorted in ascending order?

Brute Force Solution

Approach

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

Start with the number 1, which is always the first super ugly number.
Generate new numbers by multiplying existing super ugly numbers with the prime numbers provided.
Check if each newly generated number is a multiple of only the given prime numbers.
If it is, and if it's also bigger than the largest super ugly number we already have, then it's potentially a new super ugly number.
Maintain a collection of all the potential super ugly numbers and from this collection choose the smallest one as the next super ugly number.
Repeat the process of generating, checking, and selecting the next super ugly number until you have found the required number of super ugly numbers.

Code Implementation

def super_ugly_number_brute_force(number_of_ugly_numbers, primes):
    super_ugly_numbers = [1]

    while len(super_ugly_numbers) < number_of_ugly_numbers:
        potential_ugly_numbers = []
        for ugly_number in super_ugly_numbers:
            for prime_number in primes:
                new_number = ugly_number * prime_number

                # We add a new number to the pool
                potential_ugly_numbers.append(new_number)

        next_ugly_number = min(potential_ugly_numbers)

        # Check if the number is actually super ugly
        is_super_ugly = True
        temp_number = next_ugly_number
        for prime_number in primes:
            while temp_number % prime_number == 0:
                temp_number //= prime_number

        if temp_number != 1:
            is_super_ugly = False

        # Append only if it is truly super ugly
        if is_super_ugly and next_ugly_number > super_ugly_numbers[-1]:
            super_ugly_numbers.append(next_ugly_number)

        #Eliminate duplicates after adding a new super ugly number
        super_ugly_numbers = sorted(list(set(super_ugly_numbers)))

        #If we exceeded the number needed we exit the loop
        if len(super_ugly_numbers) >= number_of_ugly_numbers:
            break

    return super_ugly_numbers[number_of_ugly_numbers - 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 Super Ugly Number, which is always 1.
For each prime number given, keep track of what multiple of that prime could be the next Super Ugly Number.
Find the smallest of all these potential next Super Ugly Numbers. This is the next number in our sequence.
Add this number to our sequence of Super Ugly Numbers.
For any prime whose multiple matched the new Super Ugly Number, calculate the next multiple of that prime by multiplying it with a Super Ugly Number in the sequence.
Repeat steps 3-5 until you have found the required number of Super Ugly Numbers.

Code Implementation

def super_ugly_number(number, primes):
    ugly_numbers = [1]
    prime_indices = [0] * len(primes)

    for _ in range(1, number):
        next_ugly_numbers = [primes[i] * ugly_numbers[prime_indices[i]] for i in range(len(primes))]

        # Find the minimum potential ugly number.
        next_ugly = min(next_ugly_numbers)
        ugly_numbers.append(next_ugly)

        # Advance prime indices for multiples == min.
        for i in range(len(primes)):

            if next_ugly_numbers[i] == next_ugly:
                prime_indices[i] += 1

    return ugly_numbers[-1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty primes array	If primes is empty, return an empty list or a list containing only 1, depending on problem requirements.
n is 0 or negative	If n is 0, return an empty list; if n is negative, throw an IllegalArgumentException or return an empty list, as super ugly numbers are not defined for non-positive n.
n is 1	Return a list containing only 1 since the first super ugly number is always 1.
primes array contains duplicates	The algorithm should still work correctly as duplicates won't affect the generation of super ugly numbers if the algorithm already avoids using the same index twice.
primes array contains 1	The algorithm should handle this correctly; if 1 is in primes, the loop will iterate on 1, multiplying by 1 repeatedly but not adding to the result if already present.
Integer overflow when multiplying prime numbers	Use long data type to prevent integer overflow during multiplication of existing super ugly numbers and prime numbers.
Large n value causing memory issues	The algorithm can be optimized with generators in languages like Python or lazy evaluation to minimize memory usage for very large n.
primes array contains very large prime numbers	Using long data type will handle them, however execution time can be affected by repeated large number multiplications.

Empty primes array

How to Handle:

If primes is empty, return an empty list or a list containing only 1, depending on problem requirements.

n is 0 or negative

How to Handle:

If n is 0, return an empty list; if n is negative, throw an IllegalArgumentException or return an empty list, as super ugly numbers are not defined for non-positive n.

n is 1

How to Handle:

Return a list containing only 1 since the first super ugly number is always 1.

primes array contains duplicates

How to Handle:

The algorithm should still work correctly as duplicates won't affect the generation of super ugly numbers if the algorithm already avoids using the same index twice.

primes array contains 1

How to Handle:

The algorithm should handle this correctly; if 1 is in primes, the loop will iterate on 1, multiplying by 1 repeatedly but not adding to the result if already present.

Integer overflow when multiplying prime numbers

How to Handle:

Use long data type to prevent integer overflow during multiplication of existing super ugly numbers and prime numbers.

Large n value causing memory issues

How to Handle:

The algorithm can be optimized with generators in languages like Python or lazy evaluation to minimize memory usage for very large n.

primes array contains very large prime numbers

How to Handle:

Using long data type will handle them, however execution time can be affected by repeated large number multiplications.