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]; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter