Q62 Super Ugly Number - LeetCode 313
Sun Apr 02 2023 09:30:49 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
/* Q62 of dp playlist , every cell denotes ith ugly number . here we make
a pointers array to store pointer for all factors which are in primes
array. rest same approach as ugly numbers.
we apply 2 loops 1-> to check the minimum of all values given by factors
and 2-> to update the indexes of pointers
*/
int m = primes.length;
long[] dp = new long[n+1]; //we have to return nth ugly number
dp[1] = 1; //1 is the first ugly number
int[] pointers = new int[m];
Arrays.fill(pointers , 1); //all primes pointers points at one in begning
for(int i = 2 ; i <= n ;i++){
//1st loop to find min of all values
long min = Integer.MAX_VALUE;
for(int j = 0 ; j < m ; j++){
long valf = (long)primes[j] * (long)dp[pointers[j]];
min = Math.min(min , valf);
}
dp[i] = min; //storing min value in dp
//now incrementing indexes of pointers for primes which gave min value
for(int j = 0 ; j < m ;j++){
long valf = (long)primes[j] * (long)dp[pointers[j]];
if(valf == min)
pointers[j] ++;
}
}
// for(int i = 0 ;i <= n ; i++)
// System.out.print(dp[i] + " ");
return (int)dp[n];
}
}
content_copyCOPY
https://leetcode.com/problems/super-ugly-number/
Comments