Description:

 

What are ugly numbers?

Any number whose prime factor is only either 2,3 or 5 is an ugly number.

By convention 1 is an ugly number.

Examples: 2,3,4,5,6…….

 

Finding an Ugly Number:

 

Non DP Solution:

Loop through all positive integers

•       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 check whether 600 is ugly or not.

•       Greatest divisible power of 2 is 8,

•       after dividing 600 by 8 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.

 

Dynamic Programming- Tabulation

•       Declare an array for ugly numbers: ugly[1000]

•       Initialize first ugly no: ugly[0] = 1

•       Initialize three array index variables i2, i3, i5 to point to 1st element of the ugly array: i2 = i3 = i5 =0;

•       Initialize 3 choices for the next ugly no:

               next_mul_2 = ugly[i2]*2; next_mul_3 = ugly[i3]*3 ;next_mul_5 = ugly[i5]*5

•        Now go in a loop to fill all ugly numbers till 1000:

             For (i = 1; i < 1000; i++ )

              next_ugly_no = Min(next_mul_2, next_mul_3, next_mul_5);

              if (next_ugly_no == next_mul_of_2)

              { i2 = i2 + 1; next_mul_2 = ugly[i2]*2; }

              if (next_ugly_no == next_mul_3)

              { i3 = i3 + 1; next_mul_3 = ugly[i3]*3; }

               if (next_ugly_no == next_mul_5)

               { i5 = i5 + 1; next_mul_5 = ugly[i5]*5; }

                ugly[i] = next_ugly_no }

•       return next_ugly_no

 

C Implementation:

# include<stdio.h>
# include<stdlib.h>
 
/* Function to find minimum of 3 numbers */
unsigned min(unsigned , unsigned , unsigned );
 
/* Function to get the nth ugly number*/
unsigned getNthUglyNo(unsigned n)
{
 unsigned *ugly = (unsigned *)(malloc(sizeof(unsigned)*n));
 unsigned i2 = 0, i3 = 0, i5 = 0;
 unsigned i;
 unsigned next_mul_2 = 2;
 unsigned next_mul_3 = 3;
 unsigned next_mul_5 = 5;
 unsigned next_ugly_no = 1;
 *(ugly+0) = 1;
  for(i=1; i<n; i++)
  {
  next_ugly_no = min(next_mul_2,
  next_mul_3,
  next_mul_5);
  *(ugly+i) = next_ugly_no;                   
  if(next_ugly_no == next_mul_2)
 {
 i2 = i2+1;      
 next_mul_2 = *(ugly+i2)*2;
 }
 if(next_ugly_no == next_mul_3)
 {
  i3 = i3+1;
 next_mul_3 = *(ugly+i3)*3;
 }
 if(next_ugly_no == next_mul_5)
 {
 i5 = i5+1;
next_mul_5 = *(ugly+i5)*5;
 }
}
return next_ugly_no;
}
 
/* Function to find minimum of 3 numbers */
unsigned min(unsigned a, unsigned b, unsigned c)
{
 if(a <= b)
{
  if(a <= c)
  return a;
  else
  return c;
}
 if(b <= c)
 return b;
 else
 return c;
}

Complexity:

O(N) – time & space

Go to top