CareerCup

if x is ugly, then 2x, 3x and 5x will be ugly.

1. create a min heap(priority Queue) of 2,3 and 5
2. x = pop(heap);
3. insert(heap, 2x)
4. insert(heap, 3x)
5. insert(heap, 5x)

track the variable = size of heap + numbers popped out. When variable count reaches 1500

1. create a max heap
2. 1500thUglyNumber = pop(heap)

int findNthUgly( int N )
{
    int idx=2;
    int p2,p3,p5;
    
    p2=1,p3=1,p5=1;
    
    int DP[N+2];
    
    DP[1]=1;
    
    while( idx <=N )
    {
           
       DP[idx]=min( DP[p2]*2 , DP[p3]*3 , DP[p5]*5 );
       
       if( DP[idx]==DP[p2]*2 )
        p2++ ;
        
       else if( DP[idx]==DP[p3]*3 )
        p3++ ;
        
       else if( DP[idx]==DP[p5]*5 )
        p5++ ;
        
       
       idx++ ;
       
       }
       
   
   return DP[N] ;
   
}

You will have 3 queues for 2,3 and 5 sets.
Initially
2 -> 2Queue
3 -> 3Queue
5 -> 5Queue

then we will set an index to 0 and start the loop until it gets to 1500.

at each iteration we will check the smallest first number in the queue.
In the first iteration the number we get is from the 2Queueu. That is 2. Our second ugly number is 2 (because first ugly number is 1 :)).
At the second iteration we will multiply each of the numbers in the top of the queue by 2 and enqueue them into the queues.
2*2 -> 2Queue
3*2 ->3Queue
5*2 -> 5Queue

We have the queues like
2Queue = 4
3Queue = 3 , 6
5Queue = 5 , 10

Now we get the smallest element which is 3.

After 1500 iterations we get the 11500th ugly number.

There are 21 ugly numbers per 30 numbers (starting from 1). So, to find 1500th ugly number.
Find y = floor(1500/21). Now do z = (y*30). Z will be the (21*y) th ugly number. Now in constant time you can find the 1500th ugly number (maximum 21 steps).

What is an ugly number?

#include <vector>

typedef unsigned long long big_int;

unsigned long long FindNthUglyNumber(int n)
{
	vector<big_int> uglyNumber;
	int i, j, k, m;
	i = j = k = m = 0;

	uglyNumber.push_back(1);

	for(;;)
	{
		while(uglyNumber[i]*2 <= uglyNumber[m])
			i++;
		while(uglyNumber[j]*3 <= uglyNumber[m])
			j++;
		while(uglyNumber[k]*5 <= uglyNumber[m])
			k++;

		if(uglyNumber[i]*2 < uglyNumber[j]*3 && uglyNumber[i]*2 < uglyNumber[k]*5)
			uglyNumber.push_back(uglyNumber[i++]*2);
		else if(uglyNumber[j]*3 < uglyNumber[k]*5)
			uglyNumber.push_back(uglyNumber[j++]*3);
		else
			uglyNumber.push_back(uglyNumber[k++]*5);

		m++;
		if(m >= (n-1))
			break;
	}

	return uglyNumber.back();
}

ans is : 13668750000