InMobi Interview Question
Software Engineer / DevelopersTeam: InMobi
Country: India
Interview Type: In-Person
a sequence of ugly numbers are :
<1,2,3,4,5,6,8,9,10,12,15,16,18,20........>
Note that all number are in the form of 2^i * 3^j * 5 ^k , i.e has only the factor : 2 or 3 or 5. For example 13 is not an Ugly number. 21 is also not an Ugly number as it can't be expressed as 2^i * 3^j * 5 ^k [ 7 is a factor ] . The ugly number are in increasing order, whre 1st elemnt is 1, second element is 2, 10-th element is 12. Find out n-th Ugly number ?
Use DP.
void foo(int n)
{
static int ind2,ind3,ind5;
static int arr[30],depth;
int num2,num3,num5,num,flag=0;
if(n<=0) return;
if(depth==0)
{
ind2=ind3=ind5=0;// i know this is redundant
arr[depth++]=1;
}
num2=arr[ind2]*2;
num3=arr[ind3]*3;
num5=arr[ind5]*5;
num=min(num2,min(num3,num5));
if(num==num2)
{
ind2++;
if(arr[depth-1]!=num2)
{
flag=1;
printf("%d\n",arr[depth-1]);
arr[depth++]=num2;
}
}
else if(num==num3)
{
ind3++;
if(arr[depth-1]!=num3)
{
flag=1;
printf("%d\n",arr[depth-1]);
arr[depth++]=num3;
}
}
else
{
ind5++;
if(arr[depth-1]!=num5)
{
flag=1;
printf("%d\n",arr[depth-1]);
arr[depth++]=num5;
}
}
if(flag)
foo(n-1);
else
foo(n);
}
Complete working code: ideone.com/qz4Py
It prints first n ugly numbers.
What is the first ugly num?
- Anonymous February 19, 2012