Find the nth Ugly Number

Problem

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers. …By convention, 1 is included. Write a program to find and print the 1500’th ugly number.

Solution
Method 1 - Brute force
Loop for all positive integers until ugly number count is smaller than n, if an integer is ugly than increment ugly number count.
To check if a number is ugly, divide the number by greatest divisible powers of 2, 3 and 5, if the number becomes 1 then it is an ugly number otherwise not.
For example, let us see how to check for 300 is ugly or not. Greatest divisible power of 2 is 4, after dividing 300 by 4 we get 75. Greatest divisible power of 3 is 3, after dividing 75 by 3 we get 25. Greatest divisible power of 5 is 25, after dividing 25 by 25 we get 1. Since we get 1 finally, 300 is ugly number.

private static int maxDivide(int a, int b)  
{  
  while (a%b == 0)  
   a = a/b;   
  return a;  
}     
  
private static int isUgly(int no)  
{  
  no = maxDivide(no, 2);  
  no = maxDivide(no, 3);  
  no = maxDivide(no, 5);  
     
  return (no == 1)? 1 : 0;  
}      
   
/\* Function to get the nth ugly number\*/  
public static int getNthUglyNo(int n)  
{  
  int i = 1;   
  int count = 1;   /\* ugly number count \*/  
   
  while (n > count)  
  {  
    i++;        
    if (isUgly(i))  
      count++;   
  }  
  return i;  
}

This method is not time efficient as it checks for all integers until ugly number count becomes n, but space complexity of this method is O(1)

Method 2 - Using dynamic programming

1 Declare an array for ugly numbers:  ugly\[150\]  
2 Initialize first ugly no:  ugly\[0\] = 1  
3 Initialize three array index variables i2, i3, i5 to point to   
   1st element of the ugly array:   
        i2 = i3 = i5 =0;   
4 Initialize 3 choices for the next ugly no:  
         next\_mulitple\_of\_2 = ugly\[i2\]\*2;  
         next\_mulitple\_of\_3 = ugly\[i3\]\*3  
         next\_mulitple\_of\_5 = ugly\[i5\]\*5;  
5 Now go in a loop to fill all ugly numbers till 150:  
For (i = 1; i < 150; i++ )   
{  
    /\* These small steps are not optimized for good   
      readability. Will optimize them in C program \*/  
    next\_ugly\_no  = Min(next\_mulitple\_of\_2,  
                                  next\_mulitple\_of\_3,  
                                  next\_mulitple\_of\_5);   
    if  (next\_ugly\_no  == next\_mulitple\_of\_2)   
    {               
        i2 = i2 + 1;          
        next\_mulitple\_of\_2 = ugly\[i2\]\*2;  
    }   
    if  (next\_ugly\_no  == next\_mulitple\_of\_3)   
    {               
        i3 = i3 + 1;          
        next\_mulitple\_of\_3 = ugly\[i3\]\*3;  
     }              
     if  (next\_ugly\_no  == next\_mulitple\_of\_5)  
     {      
        i5 = i5 + 1;          
        next\_mulitple\_of\_5 = ugly\[i5\]\*5;  
     }   
     ugly\[i\] =  next\_ugly\_no         
}/\* end of for loop \*/   
6.return next\_ugly\_no  
  

```_**Example**_  
Suppose N = 50

initialize
ugly[] = | 1 |
i2 = i3 = i5 = 0;

First iteration
ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(2, 3, 5)
= 2
ugly[] = | 1 | 2 |
i2 = 1, i3 = i5 = 0 (i2 got incremented )

Second iteration
ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(4, 3, 5)
= 3
ugly[] = | 1 | 2 | 3 |
i2 = 1, i3 = 1, i5 = 0 (i3 got incremented )

Third iteration
ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(4, 6, 5)
= 4
ugly[] = | 1 | 2 | 3 | 4 |
i2 = 2, i3 = 1, i5 = 0 (i2 got incremented )

Fourth iteration
ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(6, 6, 5)
= 5
ugly[] = | 1 | 2 | 3 | 4 | 5 |
i2 = 2, i3 = 1, i5 = 1 (i5 got incremented )

Fifth iteration
ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(6, 6, 10)
= 6
ugly[] = | 1 | 2 | 3 | 4 | 5 | 6 |
i2 = 3, i3 = 2, i5 = 1 (i2 and i3 got incremented )

Will continue same way till I < 150

Here is the code in java

public static int getKthMagicNumber(int k) {
if (k <= 0)
return 0;
int val = 1;
Queue Q2 = new LinkedList();
Queue Q3 = new LinkedList();
Queue Q5 = new LinkedList();
Q2.add(2);
Q3.add(3);
Q5.add(5);
for (–k; k > 0; –k) { // We’ve done one iteration already.
val = Math.min(Q2.peek().intValue(),
Math.min(Q3.peek().intValue(), Q5.peek().intValue()));
if (val == Q5.peek()) {
Q5.remove();
} else {
if (val == Q3.peek()) {
Q3.remove();
} else { // must be from Q2
Q2.remove();
Q2.add(val * 2);
}
Q3.add(val * 3);
}
Q5.add(val * 5);
}
return val;
}

**References**  
[http://www.geeksforgeeks.org/ugly-numbers/](http://www.geeksforgeeks.org/ugly-numbers/)  
[http://stackoverflow.com/questions/4600048/nth-ugly-number](http://stackoverflow.com/questions/4600048/nth-ugly-number)  
[http://tianrunhe.wordpress.com/2012/04/03/find-the-kth-number-with-prime-factors-3-5-and-7/](http://tianrunhe.wordpress.com/2012/04/03/find-the-kth-number-with-prime-factors-3-5-and-7/)

See also