Super Ugly Number

Write a program to find the n^th super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.

Note:  1 is considered to be the first super ugly number.

Approach 1: Brute force

Main idea

We will iterate over all the natural numbers from 1 and we will maintain a count variable which will count the number of the ugly numbers we have found and the number for which count becomes equal to n, we will print that number.

How to check if a number is a super ugly number?

We will find all the prime divisors of the number and if all its prime divisors are present the given list of ‘primes’ then the number is a super ugly number and vice versa.

Approach 2: Dynamic programming 

Solution

This question is the same as merging K sorted arrays.

For example, we have

Input:  n=7 and  primes = [3, 7, 11, 13]

Output: 21

Our list will go on like this:

Algorithm

1. Declare a dp array where dp[i] represents the i^th super ugly number.
2. Initialize dp[1]=1.
3. Initialize a pointer array of size k where pointer[i] represents the pointer of the i^th prime number in the given array.
4. Run a loop, for i in range 2 to n:
   • Run a loop, for j in range 0 to k-1 to find the minimum value of dp[pointer[j]] * primes[j].
   • Update dp[i] = minimum value.
   • Iterate over pointer array and increment those indices by 1 whose value is equal to the minimum value.
5. Return dp[n].

Implementation

C++ program for nth super ugly numbers

#include <bits/stdc++.h>
using namespace std;
int nthSuperUglyNumber(int n, vector<int> &primes)
{
    vector<long long> dp(n + 1, 1);
    int k = primes.size();
    vector<int> pointer(k, 1);
    for (int i = 2; i <= n; i++)
    {
        long long mi = (1e18);
        for (int j = 0; j < k; j++)
        {
            long long temp = dp[pointer[j]] * primes[j];
            mi = min(mi, temp);
        }
        dp[i] = mi;
        for (int j = 0; j < k; j++)
        {
            long long temp = dp[pointer[j]] * primes[j];
            if (temp == mi)
            {
                pointer[j]++;
            }
        }
    }
    return dp[n];
}
int main()
{
    int n;
    cin >> n;
    int k;
    cin >> k;
    vector<int> primes(k);
    for (int i = 0; i < k; i++)
    {
        cin >> primes[i];
    }
    cout << "The nth super ugly number is: "<<nthSuperUglyNumber(n, primes) << endl;
}

7
4
3 7 11 13

The nth super ugly number is: 21

JAVA program for nth super ugly number

import java.util.*;
public class Main
{
    public static int nthSuperUglyNumber(int n,int[] primes)
    {
        int[] dp=new int[n+1];
        for(int i=0;i<=n;i++){
            dp[i]=1;
        }
        int k = primes.length;
        int[] pointer = new int[k];
        for(int i=0;i<k;i++){
            pointer[i]=1;
        }
        for (int i = 2; i <= n; i++)
        {
            int mi = Integer.MAX_VALUE;
            for (int j = 0; j < k; j++)
            {
                int temp = dp[pointer[j]] * primes[j];
                mi = Math.min(mi, temp);
            }
            dp[i] = mi;
            for (int j = 0; j < k; j++)
            {
                int temp = dp[pointer[j]] * primes[j];
                if (temp == mi)
                {
                    pointer[j]++;
                }
            }
        }
        return dp[n];
    }

  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int k = sc.nextInt();
      int[] primes = new int[k];
      for(int i=0;i<k;i++){
            primes[i] = sc.nextInt();
        }
    System.out.println("The nth super ugly number is: "+nthSuperUglyNumber(n,primes));
  }
}

6
5
2 3 5 7 17

The nth super ugly number is: 6

Complexity Analysis for nth super ugly numbers

Time complexity

There are two nested loops, first from 2 to N and second from 0 to k-1, so the time complexity is O(n*k).

Space complexity

Two arrays, one of size n and another of size k, so space complexity is O(n+k).

References