Adobe Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
DP solution
#include<stdio.h>
int getdenominations(int sum)
{
int arr[]={1,5,10,25};
int i,j;
int chan[sum+1]; //number of ways to make sum from given denominations
chan[0]=1;
chan[1]=0;
for(i=1;i<=sum;i++)
{
chan[i]=0;
for(j=0;j<4;j++)
{
if( (i-arr[j])<0 )
continue;
else
chan[i]+=chan[i-arr[j] ];
}
}
return chan[sum];
}
int main()
{
int sum=5;
printf("%d ",getdenominations(sum) );
return 0;
}
private static void MinimuumNoofCoins()
{
int[] denominations = new int[] {10,4,2,1};
int sum = 14;
int coincount = 0;
int remainder = sum;
int samecoincount = 0;
bool flag = false;
int count = 0;
for(int i = 0; remainder != 0; )
{
if (sum % denominations[i] == 0)
{
count = sum / denominations[i];
if (samecoincount != 0)
{
samecoincount = count < samecoincount ? count : samecoincount;
}
if (!flag)
{
samecoincount = count;
flag = true;
}
}
if ((remainder % denominations[i]) == 0 )
{
count = remainder / denominations[i];
remainder = remainder % denominations[i];
coincount += count;
}
if (remainder > denominations[i])
{
count = remainder / denominations[i];
remainder = remainder % denominations[i];
coincount += count;
i++;
}
else i++;
if (remainder == 0 && samecoincount!= 0) coincount = samecoincount < coincount ? samecoincount : coincount;
}
Console.WriteLine(coincount);
}
here is a backtracking approach which prints the solution as well.
ideone.com/0ioYp
- Aashish July 03, 2012