You are given an array (arr) of size k which contains prime numbers in ascending order, and an integer N.
You have to find the Nth super ugly number.
Super ugly number is defined as the number whose prime factors are elements of the given array.
Assumption: 1 is the first super ugly number.
Reader, after solving the previous problem, this question should seem fairly simple to you. We will discuss the approach for solving this problem using the input array[3,5,7,11].
APPROACH 1
To understand this problem let the input array of primes be [3,5,7,11].
Now, unlike the previous problem, we do not assign a pointer to each element of the primes array. Instead, we make a new "pointers" array with the same size as that of the "primes" array.
Each index of the "pointers" array denotes the position of the corresponding element in the "primes" array.
We also keep storing our super ugly numbers in a dp array of size N+1. Since 1 is the first super ugly number, therefore it is stored at the first index.
Initially, the pointers for all the elements will be pointing at the first super ugly number 1. Hence, we store 1 at all the indices of the "pointers" array.
Now we need to list the candidates for the next super ugly number which is obtained by multiplying each element of the "primes" array with the super ugly number at its corresponding pointer. These candidates are given in figure 5.
Out of all the possible candidates, the minimum value, 3 is our next super ugly number.
Also, the position of the selected prime element is increased by 1.
Hence, at this moment the pointer of element 3 is pointing to the super ugly number 3 and the pointers of elements 5, 7 and 11 are pointing to the super ugly number 1.
So, for calculating the next super ugly number, we again repeat the above process and multiply each prime element with the super ugly number corresponding to it and get the following candidates.
Here, the minimum value is 5, which is our next super ugly number. The position for element 5 is increased by 1.
In simple terms, we apply a loop on every element, 'j' of the "primes" array and obtain the corresponding candidates for super ugly numbers by the following formula.
This process is done till we reach the Nth super ugly number.
Reader, can you complete this process and find the 5th super ugly number (k=5).
It should come out to be equal to 9.
You can also watch the solution video to clear any gaps in the understanding of this approach.
BRUTE CODE
import java.io.*;
import java.util.*;
public class Main {
public static int solution(int[] primes, int n) {
int[]pointers=new int[primes.length];
Arrays.fill(pointers,1);
int[]dp=new int[n+1];
dp[1]=1;
for(int i=2;i<=n;i++){
int min=Integer.MAX_VALUE;
for(int j=0;j< primes.length;j++){
min=Math.min(min, primes[j]*dp[pointers[j]]);
}
dp[i]=min;
for(int j=0;j< primes.length;j++){
if(primes[j]*dp[pointers[j]]==min){
pointers[j]++;
}
}
}
return dp[n];
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int k = scn.nextInt();
int[] primes = new int[k];
for (int i = 0 ; i < k; i++) {
primes[i] = scn.nextInt();
}
int n = scn.nextInt();
System.out.println(solution(primes, n));
}
}
java;
true";
In the above method we simply follow the given approach without the use of an extra Pair class. This method is quite straightforward.
Analysis
Time Complexity:
O(n2)
Since we are using nested loops in this approach, therefore the complexity is quadratic.
Space Complexity:
O(n)
The space complexity is linear because extra space is required for the "dp" array and the "pointers" array.
OPTIMISED CODE
We feel a need to optimize the above code due to its high time complexity.
import java.io.*;
import java.util.*;
public class Main {
public static class Pair implements Comparable< Pair>{
int prime;
int pointer;
int value;
public Pair(int prime, int pointer, int value){
this.prime=prime;
this.pointer=pointer;
this.value=value;
}
public int compareTo(Pair o){
return this.value-o.value;
}
}
public static int solution2(int[]primes,int n){
int[]dp=new int[n+1];
PriorityQueue< Pair> pq=new PriorityQueue< >();
for(int i=0;i< primes.length;i++){
pq.add(new Pair(primes[i],1,primes[i]));
}
dp[1]=1;
for(int i=2;i<=n;){
Pair rp=pq.remove();
if(dp[i-1]!=rp.value){
dp[i]=rp.value;
i++;
}
pq.add(new Pair(rp.prime,rp.pointer+1,rp.prime*dp[rp.pointer+1]));
}
return dp[n];
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int k = scn.nextInt();
int[] primes = new int[k];
for (int i = 0 ; i < k; i++) {
primes[i] = scn.nextInt();
}
int n = scn.nextInt();
System.out.println(solution2(primes, n));
}
}
java;
true";
In the second method, we introduce a Pair class which has 3 data members, "prime", "pointer" and "value". We use a priority queue of type "Pair" instead of using a "pointers" array.
You can understand a detailed explanation of this code from the solution video.
Optimised Time & Space Complexity
Time Complexity:
O(nlogk)
The size of a priority queue remains fixed i.e. k. In this priority queue, we use the "add" and "remove" functions which take a time of logk. Hence the total optimized time complexity of the program is O(nlogk).
Space Complexity:
O(n+k)
In this complexity, n is the size of the dp array and k is the size of the priority queue.
With this we conclude our problem. We sincerely hope you enjoyed solving this problem with us.
