Super Ugly Number  

Difficulty Level Medium
Frequently asked in Google
Heap Math

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?

Please click Like if you loved this article?

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 NumberPin

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].
See also
Find whether a subarray is in form of a mountain or not

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

See also
Print Ancestors of a Given Binary Tree Node Without Recursion

Space complexity

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

References

Please click Like if you loved this article?