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