Same solution as Ugly Number II


  • 0
    S

    If you understand the solution for https://leetcode.com/problems/ugly-number-ii/, this solution is exactly the same.

    For the ugly number II problem, this is an accepted solution

    public class Solution {

    public int nthUglyNumber(int n) {
        
    int[] ugly= new int[n];
    
    ugly[0] = 1;
    int factor2=2, factor3=3,factor5=5;
    int ind2=0,ind3=0,ind5=0;
    
    for(int i=1;i<n;i++)
    {
        int min = Math.min(factor2,Math.min(factor3,factor5));
        
        ugly[i]=min;
        
        if(min==factor2)
        {
            factor2=2*ugly[++ind2];
        }
        if(min==factor3)
        {
            factor3=3*ugly[++ind3];
        }
        if(min==factor5)
        {
            factor5=5*ugly[++ind5];
        }
    }
    
    return ugly[n-1];
        
    }
    

    }

    The solution to this problem is same, except that instead of 3 numbers you have k numbers to consider. To achieve this, you declare the initial variables as an array. Here is an accepted solution for this problem.
    Notice, the logic is same for both.

    public class Solution {

    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
    
        int len=primes.length;
    
        ugly[0] = 1;
    
       // This tracks the array
        int[] index = new int[len];
    
        int[] factor = new int[len];
        System.arraycopy(primes,0,factor,0,factor.length);
        // Initialilze the factors
    
        for(int i=1;i<n;i++){
           
           int min=Integer.MAX_VALUE;
           for(int j=0;j<len;j++)
           {
               min=Math.min(min,factor[j]);
           }
              
            ugly[i] = min;
            
            for(int j=0;j<len;j++)
            {
                if(min==factor[j])
                {
                    factor[j]=primes[j]*ugly[++index[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.