Home » Technical Interview Questions » Dynamic Programming Interview Questions » Super Ugly Number

Super Ugly Number


Reading Time - 3 mins

Write a program to find the nth 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:

Super Ugly Number

Algorithm

  1. Declare a dp array where dp[i] represents the ith super ugly number.
  2. Initialize dp[1]=1.
  3. Initialize a pointer array of size k where pointer[i] represents the pointer of the ith 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].
READ  Decode Ways

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).

READ  Pascal Triangle Leetcode

Space complexity

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

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions