Fastest Nth Ugly Number (Ugly Number II)and Super Ugly Number similar solutions, Java Dynamic Programming


  • 1
    S

    Nth Ugly Number Solution: -

    public class Solution {
        public int nthUglyNumber(int n) {
            if(n <= 0) {
                return 0;
            }
            int[] ugly = new int[n];
            ugly[0] = 1;
            int index2 = 0, index3 = 0, index5 = 0;
            int factor2 = 2, factor3 = 3, factor5 = 5;
            int curMin = 1;
            for(int i = 1; i < n; ++i) {
                curMin = Math.min(factor2, Math.min(factor3, factor5));
                ugly[i] = curMin;
                if(factor2 == curMin){
                    factor2 = 2*ugly[++index2];
                }
                if(factor3 == curMin){
                    factor3 = 3*ugly[++index3];
                }
                if(factor5 == curMin){
                    factor5 = 5*ugly[++index5];
                }
            }
            return ugly[n-1];
        }
    }
    

    Super Ugly Number Solution. Since we do not know what the prime factors will be, we will have to create 2 arrays for that.

    public class Solution {
        public int nthSuperUglyNumber(int n, int[] primes) {
    	if(n <= 0 || primes == null || primes.length == 0) {
    		return 0;
    	}
    
    	int[] ugly = new int[n];
    	ugly[0] = 1;
    	int length = primes.length;
    	int[] indexes = new int[length];
    	int[] factors = new int[length];
    	for(int i = 0; i < length; ++i) {
    		factors[i] = primes[i];
    	}
    	int curMin = 1;
    	for(int i = 1; i < n; i++){
    		curMin = factors[0];
    		for(int j = 1; j < length; ++j) {
    			curMin = Math.min(curMin, factors[j]);
    		}
    		ugly[i] = curMin;
    		for(int j = 0; j < length; ++j) {
    			if(curMin == factors[j]) {
    				factors[j] = primes[j] * ugly[++indexes[j]];
    			}
    		}
    	}
    	return ugly[n-1];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.