6Companies30days

Ugly Numbers

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return the nth ugly number.

Example

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Video Explanation

Naive approach - to check for ugly numbers and keep building till the end ( exponential complexity ) ( O(n^n) )

 vector <int> sieve;
    
    bool checkUgliness(int n){
        
        vector <int> ugliPrimes = {2,3,5};
        
        for(auto prime:sieve) {
            if( n % prime == 0 ) {
                return false;
            }
        }
        
        for(auto prime: ugliPrimes){
            if( n % prime == 0 ) {
                return true;
            }
        }

        sieve.push_back(n);
        return false;
        
    }
    
    
    
    int nthUglyNumber(int n) {
        
        if( n == 1 ) return 1;

        int uglyCnt = 1;
        int i = 2;
        int currUgly = 1;
        while( uglyCnt < n ){      
            if(checkUgliness(i)) {
                uglyCnt++;
                currUgly = i;
            }
            i++;         
        }
          
        return currUgly;
        
        
    }

Using sets ( O(nlogn) )

Idea is to maintain a set to quickly find the smallest element in O(logn) and maintain unique set.
triplets = {2,3,5} maintain a pointer to the minimum element
the current minimum element is the ith Ugly Number
To find the (i+1)th Ugly Number multiply the current ugly number by 2,3,5 and push the triplet in the set and delete the current ugly number.
Now revaluate the current ugly number from the set
Be careful of overflows as curr*5 > INT_MAX

Code -

 int nthUglyNumber(int n) {        

     set <int> store = {2,3,5};
     int ugly = 1;
     int i = 2;
     vector <int> triplets = {2,3,5};

     while( i <= n ){

         long int curr = *store.begin();
         ugly = curr;
         i++;

         for( auto num : triplets) {   
             long int temp = curr*num;
             if( temp > INT_MAX ) continue;
             store.insert(temp);
       }

      store.erase(curr);
    }
    
    return ugly;
}

This approach can be improved by using a priority queue instead of a set.

Optimal Solution | DP | Prime Factors

Idea

The key is to realize each number can be and have to be generated by a former number multiplied by 2, 3 or 5 e.g. 1 2 3 4 5 6 8 9 10 12 15.. what is next? it must be x * 2 or y * 3 or z * 5, where x, y, z is an existing number.

How do we determine x, y, z then? apparently, you can just traverse the sequence generated by far from 1 … 15, until you find such x, y, z that x * 2, y * 3, z * 5 is just bigger than 15. In this case x=8, y=6, z=4. Then you compare x * 2, y * 3, z * 5 so you know next number will be x * 2 = 8 * 2 = 16. k, now you have 1,2,3,4,….,15, 16,

Then what is next? You wanna do the same process again to find the new x, y, z, but you realize, wait, do I have to traverse the sequence generated by far again?

NO! since you know last time, x=8, y=6, z=4 and x=8 was used to generate 16, so this time, you can immediately know the new_x = 9 (the next number after 8 is 9 in the generated sequence), y=6, z=4. Then you need to compare new_x * 2, y * 3, z * 5. You know next number is 9 * 2 = 18;

And you also know, the next x will be 10 since new_x = 9 was used this time. But what is next y? apparently, if y=6, 6*3 = 18, which is already generated in this round. So you also need to update next y from 6 to 8.

Based on the idea above, you can actually generated x,y,z from very beginning, and update x, y, z accordingly. It ends up with a O(n) solution.

PS

We have an array k of first n ugly number. We only know, at the beginning, the first one, which is 1. Then
k[1] = min( k[0]x2, k[0]x3, k[0]x5). The answer is k[0]x2. So we move 2’s pointer to 1. Then we test:
k[2] = min( k[1]x2, k[0]x3, k[0]x5). And so on. Be careful about the cases such as 6, in which we need to forward both pointers of 2 and 3.
x here is multiplication.

int nthUglyNumber(int n) {        

    int two = 0 , three = 0 , five = 0 ;
    vector <int> ugly(n+1,0);
    ugly[0] = 1;

    for( int i = 1 ; i <=n ; i++ ){

        ugly[i] = min({ugly[two]*2 , ugly[three]*3 , ugly[five]*5 });
        if(ugly[i] == ugly[two]*2 ) two++;
        if(ugly[i] == ugly[three]*3 ) three++;
        if(ugly[i] == ugly[five]*5 ) five++;

    }

    return ugly[n-1];
}

Credits -

LeetCode Explain

Leetcode