Super Ugly Number

Question

So the problem is:

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. For example, [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] of size 4.

So my algorithm basically finds all possible factors using the pattern they follow, pushes them to an array, sorts that array and then returns the nth value in the array. It accurately calculates all of them, however, is too slow with high nth values.

My question is what the proper way to do this is as I'm sure there has to be a more straightforward solution. I'm mostly curious about the theory behind finding it and if there's some kind of closed formula for this.

 var nthSuperUglyNumber = function(n, primes) {
     xprimes = primes;
     var uglies = [1];
     uglies = getUglyNumbers(n, primes, uglies);
     // return uglies[n-1];
     return uglies[n - 1];
 };

 //                     3                         4
 //1, 2,3,5, || 4,6,10, 9,15, 25, || 8,12,20,18,30,50, 27,45,75, 125 ||
 //   3,2,1     6,3,1,               10,4,1
 //              1            1              1
 //1, 2,3 || 4,6, 9, || 8,12,18, 27 || 16,24,36,54, 81
 //   2,1    3,1        4,1            5,1
 //
 //1, 2,3,5,7 || 4,6,10,14 9,15,21 25,35, 49 ||
 //   4,3,2,1 || 10,6,3,1

 var getUglyNumbers = function(n, primes, uglies) {
     if (n == 1) {
         return uglies;
     }
     var incrFactor = [];

     var j = 0;
     // Initial factor and uglies setup
     for (; j < primes.length; j += 1) {
         incrFactor[j] = primes.length - j;
         uglies.push(primes[j]);
     }

     //recrusive algo
     uglies = calcUglies(n, uglies, incrFactor);
     uglies.sort(function(a, b) {
     return a - b;
     });
     return uglies;
 };

 var calcUglies = function(n, uglies, incrFactor) {
     if (uglies.length >= 5 * n) return uglies;
     var currlength = uglies.length;
     var j = 0;
     for (j = 0; j < xprimes.length; j += 1) {
         var i = 0;
         var start = currlength - incrFactor[j];
         for (i = start; i < currlength; i += 1) {
             uglies.push(xprimes[j] * uglies[i]);
         }
     }
     // Upgrades the factors to level 2
     for (j = 1; j < xprimes.length; j += 1) {
         incrFactor[xprimes.length - 1 - j] = incrFactor[xprimes.length - j] + incrFactor[xprimes.length - 1 - j];
     }

     return calcUglies(n, uglies, incrFactor);
 };

Answer 1

This is the most optimal solution I could write using Dynamic Programming in Python.

Time complexity: O(n * k)

Space Complexity: O(n)

from typing import List


def super_ugly_numbers(n: int, primes: List[int]) -> int:
    # get nth super ugly number
    ugly_nums = [0] * n
    ugly_nums[0] = 1
    length = len(primes)
    mul_indices = [0] * length
    multipliers = primes[:]

    for index in range(1, n):
        ugly_nums[index] = min(multipliers)

        for in_index in range(length):
            if ugly_nums[index] == multipliers[in_index]:
                mul_indices[in_index] += 1
                multipliers[in_index] = ugly_nums[mul_indices[in_index]] * primes[in_index]

    return ugly_nums[n-1]

Answer 2

public static ArrayList<Integer> superUgly(int[] primes,int size)
{
    Arrays.sort(primes);
    int pLen = primes.length;

    ArrayList<Integer> ans = new ArrayList<>();
    ans.add(1);

    PriorityQueue<pair> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(p -> p.value));
    HashSet<Integer> hashSet = new HashSet<>();

    int next_ugly_number;
    int[] indices = new int[pLen];

    for(int i=0;i<pLen;i++) {
        hashSet.add(primes[i]);
        priorityQueue.add(new pair(i,primes[i]));
    }

    while(ans.size()!=size+1)
    {
        pair pair = priorityQueue.poll();
        next_ugly_number = pair.value;
        ans.add(next_ugly_number);
        indices[pair.index]+=1;

        int temp = ans.get(indices[pair.index])*primes[pair.index];
        if (!hashSet.contains(temp))
        {
            priorityQueue.add(new pair(pair.index,temp));
            hashSet.add(temp);
        }
        else {
            while(hashSet.contains(temp))
            {
                indices[pair.index]+=1;
                 temp = ans.get(indices[pair.index])*primes[pair.index];

            }
            priorityQueue.add(new pair(pair.index,temp));
            hashSet.add(temp);

        }

    }

    ans.remove(0);
    return ans;
}

Pair class is

class pair
{
    int index,value;
    public pair(int i,int v)
    {
        index = i;
        value = v;
    }
}

It returns a list of ugly numbers of size 'size'.
I am using priority queue to find minimum for every loop and also a hashset to avoid duplicate entries in priorityQueue.
So its time complexity is O(n log(k)) where n is size and k is primes array size.

Answer 3

This algorithm performs better for large n.

primes := {2, 7, 13, 19}
set list := {1}
for i in 1..n-1:
  set k = list[0]
  for p in primes:
    insert p*k into list unless p*k is in list
  remove list[0] from list
return list[0]

If inserting in order is hard, you can just insert the elements into the list at the end and sort the list just after removing list[0].

Answer 4

import java.util.*;
import java.lang.*;
import java.io.*;
public  class Solution{

    public static void main(String[] args) {
        Scanner fi = new Scanner(System.in);
        int n=fi.nextInt();
        int i;
        int primes[] ={2,3,5};
        HashSet<Integer> hm=new HashSet<>();
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        TreeSet<Integer> tr=new TreeSet<>();
        tr.add(1);
        pq.add(1);
        hm.add(1);

        for (i=0;i<primes.length;i++){
            tr.add(primes[i]);
            pq.add(primes[i]);
            hm.add(primes[i]);
        }
        int size=tr.size();
        while (size < n){
            int curr=pq.poll();
            for (i=0;i<primes.length;i++){
                if (!hm.contains(curr*primes[i])) {
                    tr.add(curr * primes[i]);
                    hm.add(curr*primes[i]);
                    pq.add(curr*primes[i]);
                    size++;
                }
            }

        }
        System.out.println(tr);
    }
}

This might as Help as TreeSet maintains element in sorted order so need to worry about index.