Taro Logo

Super Ugly Number

Medium
Google logo
Google
Topics:
ArraysDynamic Programming

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 nth super ugly number.

For example:

  1. If n = 12 and primes = [2, 7, 13, 19], what is the 12th super ugly number? The sequence of the first 12 super ugly numbers is: [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]. Therefore, the answer is 32.
  2. If n = 1 and primes = [2, 3, 5], what is the 1st super ugly number? The answer is 1.

Write a function to find the nth super ugly number given n and primes.

Solution


Super Ugly Number Problem

Problem Description

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 nth super ugly number. The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

For example:

  • n = 12, primes = [2, 7, 13, 19] => Output: 32. The sequence is [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32].
  • n = 1, primes = [2, 3, 5] => Output: 1

Naive Approach

A brute force solution would involve generating all possible numbers and checking if they are super ugly numbers. This is highly inefficient.

Optimal Approach

We can use dynamic programming to solve this problem efficiently. We maintain an array ugly to store the super ugly numbers, and an array pointers to track the index of each prime number in the ugly array. For each index i from 1 to n-1, we find the minimum value among ugly[pointers[j]] * primes[j] for all j and update the ugly array. If a prime number generates the minimum ugly number, its corresponding pointer is incremented. This approach ensures that we only consider the necessary multiplications, and reduces time complexity.

def nthSuperUglyNumber(n, primes):
    ugly = [0] * n
    ugly[0] = 1
    pointers = [0] * len(primes)

    for i in range(1, n):
        min_ugly = float('inf')
        for j in range(len(primes)):
            min_ugly = min(min_ugly, ugly[pointers[j]] * primes[j])
        ugly[i] = min_ugly

        for j in range(len(primes)):
            if ugly[pointers[j]] * primes[j] == min_ugly:
                pointers[j] += 1

    return ugly[n - 1]

Edge Cases

  • n = 1: should return 1.
  • primes is empty. (Problem statement guarantees primes.length >= 1.)
  • Large values of n that might cause integer overflow (problem statement guarantees a 32-bit signed integer)

Time and Space Complexity

  • Time Complexity: O(n * k), where n is the nth super ugly number to find and k is the number of primes.
  • Space Complexity: O(n + k), where n is for the ugly array and k is for the pointers array.