Adobe Interview Question Software Engineer / Developers
Country: India
We can use the greedy approach as well but that doesn't always lead to the right solution.
recursive version
// Returns the min count of coins required to make a given change = amount
int coin_change(int change_amount, int val[], int n)
{
assert(change_amount>=0 && n>=0);
if(change_amount==0) return 0; // No coins required.
if(n==0) return INT_MAX;
if(val[n-1] > change_amount) return coin_change(change_amount, val, n-1);
// assuming infinite coins of each denominations (notice the first call with n again)
return min( coin_change(change_amount-val[n-1], val, n),
coin_change(change_amount, val, n-1) );
}
Another approach based on DP[Modification of cutting of rod].
This method doesn't require the coin[]={1,3,10} to be sorted.
Say, we know the number of coins required for n-1, we can extend it for n also.
1. Take a minCount array. If minCount[i]==j, then minimum of j number of coins are required for i.
void countCoins(int* coin,int size,int tofind)
{
int minCount[tofind+1],i,j,mintillnow;
for(i=0;i<tofind+1;++i)
minCount[i]=0;
for(i=0;i<size;i++)
if(coin[i]<=tofind)
minCount[coin[i]]=1;
for(i=1;i<=tofind;i++)
{
if(!minCount[i])
{
mintillnow=INT_MAX;
for(j=1;j<i;++j)
{
if(minCount[j]+minCount[i-j]<mintillnow)
mintillnow=minCount[j]+minCount[i-j];
}
minCount[i]=mintillnow;
}
}
printf("Minimum number of coins needed is: %d",minCount[tofind]);
}
The only disadvantage of this method is that it may require large amount of space.
e.g. we may need change of Rs 1 lakh[space required is 1lakh bytes]. However, it can be reduced if we go for bit-vector.
Complete code here: ideone.com/pKEwC
It is the simple one.
Assuming that the coin array is sorted in ascending order[1,3,10].
Time complexity: O(N)
Space complexity: O(1)
Here is the code
// to find the change of k.
int countCoins(int* coin,int size,int value)
{
int i,count,total=0;
for(i=size-1;i>=0;i--)
{
count=value/coin[i];
if(count)
{
value-=count*coin[i];
total+=count;
printf("%d number of Rs %d coins\n",count,coin[i]);
}
}
return total;
}
int main()
{
int coin[]={1,3,10},size,k;
size=sizeof(coin)/sizeof(coin[0]);
scanf("%d",&k);
printf("Minimum pickings: %d",countCoins(coin,size,k));
return 0;
}
ideone.com/Tr69T
int getMinPicks(int []numbers, int target){
int minIndex = numbers.length -1;
int result = target/numbers[minIndex];
target = target%numbers[minIndex];
while(target!= 0){
if(minIndex == 0)
return -1;
result+=(target/numbers[--minIndex]);
target = target%numbers[minIndex];
}
return result;
}
I've compiled and tested this C++ code. The input array doesn't need to be sorted. Also prints the elements that add up to the target sum.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main ( ) {
int val, target;
int index = 0; /* Current array index */
int minpick = 10000; /* Initialize to a high value */
vector<int> arr; /* The vector holding the elements */
/* Temporary vector and the vector holding the minimum set */
vector<int> temp, min;
cout << endl << "Enter the array elements. End with EOF (ctrl + D)" << endl;
while (cin >> val)
arr.push_back(val);
/* Clear the cin buffer */
cin.clear();
cout << endl << "Enter the target sum: ";
cin >> target;
/* Sort the array */
sort(arr.begin(), arr.end());
/* Assumption made that the target itself
* doesn't exist in the array. Would be better
* if that edge-case is added too. */
while (index < arr.size() && arr[index] < target) {
int sum = arr[index]; /* Sum of array elements */
int i = index + 1;
int count = 1; /* Count of elements that add up to target */
temp.push_back(arr[index]);
while (i < arr.size() && sum < target) {
sum = sum + arr[i];
temp.push_back(arr[i]);
count++;
if (sum >= target) {
if (sum == target) {
if (count < minpick) {
/* Least number of elements maintained
* in minpick variable */
minpick = count;
/* Copy the elements adding up to target
* from temp to the min vector */
min.assign (temp.begin(), temp.end());
}
}
/* Pop the last two elements from the temp
* vector and take them off from sum. This
* is needed to move on and try out other
* possible combinations. */
sum = sum - temp.back(); temp.pop_back();
sum = sum - temp.back(); temp.pop_back();
count = count - 2;
if (sum == 0) break;
}
else {
i++;
}
}
temp.clear();
index++;
}
if (minpick == 10000) {
cout << endl << "No combination exists." << endl << endl;
return 0;
}
cout << endl;
for (vector<int>::iterator it = min.begin(); it != min.end(); it++) {
cout << *it << " ";
}
cout << endl << "Minimum picks = " << minpick << endl << endl;
return 0;
}
With some assumption the code can be done.
1. We will pick the coin only once - ie. no duplicates
2. The array is ordered - or sorting is needed
#include<stdio.h>
void main()
{
int test1[] = {1,2,3,4,5,6};
int test2[] = {1,3,10};
//assuming the sorted array is given
//otherwise it has to ordered.
printf("%d \n", minimum_pick(test1, 6, 15)); //printed 3
printf("%d \n", minimum_pick(test2, 3, 11)); //printed 2
}
int minimum_pick(int *numbers, int size, int sum)
{
int tot = 0, count = 0;
if (sum == 0)
{
return 0;
}
else
{
//loop until you attain the max sum
while(size > -1)
{
if (tot + numbers[size-1] < sum)
{
count++;
tot += numbers[size-1];
}
else if (tot + numbers[size-1] == sum)
{
count++;
break;
}
size--;
}
}
return count;
}
ethioer : Your code is just checking whether how many numbers were fit together. You does not actually checking whether the particular sum is present or not!
please check with the input 4, 6, 8, 9 and the sum required is 11. Your code is giving 2 as answer.
adjustment to the previous solution.
The first has a flaw. it can be done with O(n^2) as follows with some test case
it is done in c
#include<stdio.h>
void main()
{
int test1[] = {1,2,3,4,5,6};
int test2[] = {1,3,10};
int test3[] = {1,3,4,5,6};
//assuming the sorted array is given
//otherwise it has to ordered.
printf("%d shall print 3\n", minimum_pick(test1, 6, 15));
printf("%d shall print 2\n", minimum_pick(test2, 3, 11));
printf("%d shall print 1\n", minimum_pick(test3, 5, 4));
printf("%d shall print 2\n", minimum_pick(test3, 5, 7));
printf("%d shall print 3\n", minimum_pick(test3, 5, 14));
}
int minimum_pick(int *numbers, int length, int sum)
{
int tot = 0, count = 0, min = 1000;;
if (sum == 0)
{
return 0;
}
else
{
int index = length - 1;
//loop until you attain the max sum
while(index >= 0)
{
tot = numbers[index], count=1;
if (tot == sum)
{
return count; //one is the minimum
}
else if (numbers[index]>sum)
{
index--;
continue;
}
int inner_index = index - 1, found=0;
while(inner_index >= 0)
{
if (tot + numbers[inner_index] < sum)
{
count++;
tot += numbers[inner_index];
}
else if (tot + numbers[inner_index] == sum)
{
count++;
found=1;
break;
}
inner_index--;
}
if (found && count < min)
{
min = count;
}
index--;
}
}
return min;
}
int main()
{
int numOfDenominations = 0;
cout << "Please put in the number of denominations available " << endl;
cin >> numOfDenominations;
int * denominations = new int[numOfDenominations];
memset(denominations , 0 , sizeof(int) * numOfDenominations);
int sumNeeded = 0;
cout << "Please enter the sum for which the change is needed " << endl;
cin >> sumNeeded;
int * optimumDenominationCount = new int[sumNeeded+1];
int * optimumDenomination = new int [sumNeeded+1];
for (int i =0 ; i < sumNeeded+1 ; i ++)
{
optimumDenominationCount[i] = 10000;
optimumDenomination[i] = 10000;
}
cout << "Please put in the denominations " << endl;
for (int i = 0 ; i < numOfDenominations ; i++)
{
cin >> denominations[i];
if(denominations[i] <= sumNeeded )
{
optimumDenomination[(denominations[i])] = (denominations[i]);
optimumDenominationCount[(denominations[i])] = 1;
}
}
for (int i = 1 ; i <= sumNeeded ; i++)
{
for (int j = 0 ; j < numOfDenominations ; j ++)
{
if(i-denominations[j] > 0)
{
if(optimumDenominationCount[i] > optimumDenominationCount[i-denominations[j]] + 1)
{
optimumDenominationCount[i] = optimumDenominationCount[i-denominations[j]] + 1;
optimumDenomination[i] = denominations[j];
}
}
}
}
if(optimumDenominationCount[sumNeeded] == 10000)
{
cout << "Change cannot be provided " << endl;
}
else
{
cout << " The count is = " << optimumDenominationCount[sumNeeded] << endl;
cout << "The coins needed are " << endl;
int temp = sumNeeded;
while(temp > 0)
{
cout << optimumDenomination[temp] << endl;
temp = temp - optimumDenomination[temp];
}
}
}
/* Sort the Input Array using any Sorting Algorithm and pass it as an I/P arg to FindSum() */
int FindSum (int *p_array, int req_sum, int num_elements)
{
int index = INVALID_VAL;
int num_picks = 0;
char flag = NOT_SET;
/* Find the Maximum Array Element which is <= req_sum */
for (index = num_elements-1; index < num_elements && p_array[index]>=req_sum; index--)
{
if (p_array[index] == req_sum)
{
flag = SET;
break;
}
}
if (index>=0 && index<MAX_SIZE)
{
num_picks++;
printf ("\nElement Added: %d\n", p_array[index]);
}
/* Now, p_array[index] = maximum array value < req_sum */
if (!flag)
{
num_picks = num_picks + FindSum(p_array, req_sum-p_array[index], num_elements);
}
return num_picks;
}
int main()
{
int numbers[]={1,2,4,5,6};
int target = 9, len = 5;
int final_result = 999, temp_result = 0;
while(len > 0)
{
temp_result = 0;
temp_result = findsum(numbers,target,len,temp_result);
if( final_result > temp_result)
{
final_result = temp_result;
}
len--;
}
printf("\nFinal result is %d", final_result);
}
int findsum(int numbers[], int target, int len, int temp_result)
{
if(target == 0)
return temp_result;
if(len>=0)
{
if((target - numbers[len-1]) >= 0)
{
temp_result++;
return findsum(numbers,target-(numbers[len-1]), len-1, temp_result);
}
else
return findsum(numbers,target, len-1, temp_result);
}
}
int MAX_NO_PICKS = Integer.MAX_VALUE;
//Pass any unsorted array, sum to check,no of picks pass 0, baseIndex pass 0
int getNumberOfPicks(int[] coinArr, int sum, int noOfPicks, int baseIndex){
if(noOfPicks+1 >= MAX_NO_PICKS && sum !=0){
return -1;
}else if(sum == 0){
MAX_NO_PICKS = noOfPicks;
return noOfPicks;
}
if(sum < 0) return -1;
if(baseIndex >= coinArr.length) return -1;
int tempSum = sum - coinArr[baseIndex];
int choosenPick = getNumberOfPicks(coinArr, tempSum, noOfPicks+1,baseIndex+1);
int notChoosenPick = getNumberOfPicks(coinArr, sum, noOfPicks,baseIndex+1);
//System.out.println(choosenPick +" "+notChoosenPick);
if(choosenPick == -1 && notChoosenPick == -1){
return -1;
}else if(choosenPick == -1){
return notChoosenPick;
}else if(notChoosenPick == -1){
return choosenPick;
}else{
if(choosenPick < notChoosenPick){
return choosenPick;
}else{
return notChoosenPick;
}
}
}
Array should be sorted
{
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void PrintArray(int* A, int* B, int arr_size)
{
printf("\n Picking Coins \n");
for(int i = 0; i <arr_size; i++)
{
printf("\n A[i] %d :: B[i] %d \n", A[i], B[i]);
}
return;
}
int SolveEquation(int* A, int* B, int total, int size, int arr_size, int coins )
{
static int min_coins = total;
if(size == 0)
{
if(total % A[size] == 0)
{
B[size] = total/A[size];
total = total - A[size]*B[size];
if(coins +B[size] < min_coins)
{
printf("\n current min coins %d min_coins %d \n", coins, min_coins);
min_coins = coins;
PrintArray(A, B, arr_size);
}
}
return min_coins;
}
int max = total/A[size];
for(int j = max; j >= 0; j--)
{
if(coins+j > min_coins)
break;
B[size] = j;
SolveEquation(A, B, total - A[size]*j , size-1, arr_size, coins+j);
}
return min_coins;
}
}
this works!
int minimum_pick(int *numbers, int size, int sum)
{
int tot = 0, count = 0,s=size;
if (sum == 0)
{
return 0;
}
else
{
//loop until you attain the max sum
while(size > 0)
{
if (tot + numbers[size-1] < sum)
{
count++;
tot += numbers[size-1];
}
else if (tot + numbers[size-1] == sum)
{
count++;
break;
}
else if(size<=1)
{
size=s--;
count=0;
tot=0;
}
size--;
}
}
return count;
}
int main()
{
int test1[] = {1,2,3,4,5,6};
int test2[] = {5,6,9};
//assuming the sorted array is given
//otherwise it has to ordered.
printf("%d \n", minimum_pick(test1, 6, 15)); //printed 3
printf("%d \n", minimum_pick(test2, 3, 11)); //printed 2
return 0;
}
#include<stdio.h>
int count(int *coin , int len , int sum)
{
int tot , min = 10000;
int i ;
for( i = len - 1 ; i >= 0 ; i--)
{
tot = 0 ;
int sum1 = sum;
int j ;
int val;
for( j = i ; j >= 0 ; j--)
{
val = sum1/coin[j] ;
tot += val;
int sum2 = coin[j] * val;
if(sum1 == sum2)
{
break;
}
sum1 -= val*coin[j] ;
}
if( tot < min)
min = tot;
}
return min;
}
int main()
{
int coin[] = {1,3,10};
int size,sum;
scanf("%d",&sum);
size=sizeof(coin)/sizeof(coin[0]);
printf("Min No. of coins = %d",count(coin,size,sum));
return 0;
}
//Given coin array and a sum K, find min. number of required coin to make sum K.
#include<stdio.h>
#include<conio.h>
main()
{
int a[20],n,i,k,j,b=0,max,sum=0;
printf("enter no of coin\n");
scanf("%d",&n);//no of coin
printf("\n enter coin\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);//enter arrat
printf("enter sum of money");
scanf("%d",&k);//enter money
for(i=0;i<n;i++)
sum=sum+a[i];
if(sum<k)//if sum of money is grester then the sum of array
printf("not possible");
else
{
while(k>0)
{max=0;
for(i=0;i<n;i++)
{
if(max<a[i]&&k>=a[i])
{
max=a[i];
j=i;
}}
k=k-max;
printf("%d ",a[j]);
a[j]=0;
b++;
}
printf("\n no of coin==%d\n",b);
}
getch();
}
((( #include<stdio.h>
int reqd(int *a, int siz, int sum)
{
int i;
if(a[siz - 1] > sum && siz > 0)
{
//printf("A%d ", a[siz - 1]);
return reqd(a, siz-1, sum);
}
else if(a[siz - 1] == sum && siz > 0)
{
printf("B%d ", a[siz - 1]);
return (1);
}
else if(a[siz - 1] < sum && siz > 0)
{
printf("C%d ", a[siz - 1]);
i = reqd(a, siz, sum - a[siz - 1]);
if(i <0 )
return reqd(a, siz-1, sum);
else return (1 + i);
}
else
printf("failed ");
return -1;
}
main()
{
int ar[] = {3,5,7,11}; // sorted array
int siz = 4; //size of above array
int sum=0,j=0;
scanf("%d", &sum);
j = reqd(ar, siz, sum);
printf("\n%d", j);
}
)))
#include<stdio.h>
int reqd(int *a, int siz, int sum)
{
int i;
if(a[siz - 1] > sum && siz > 0)
{
//printf("A%d ", a[siz - 1]);
return reqd(a, siz-1, sum);
}
else if(a[siz - 1] == sum && siz > 0)
{
printf("B%d ", a[siz - 1]);
return (1);
}
else if(a[siz - 1] < sum && siz > 0)
{
printf("C%d ", a[siz - 1]);
i = reqd(a, siz, sum - a[siz - 1]);
if(i <0 )
return reqd(a, siz-1, sum);
else return (1 + i);
}
else
printf("failed ");
return -1;
}
main()
{
int ar[] = {3,5,7,11}; // sorted array
int siz = 4; //size of above array
int sum=0,j=0;
scanf("%d", &sum);
j = reqd(ar, siz, sum);
printf("\n%d", j);
}
The below code does it recursively. It shows failure message if the sum is not possible to obtain from the given denominations.
#include<stdio.h>
int reqd(int *a, int siz, int sum)
{
int i;
if(a[siz - 1] > sum && siz > 0)
{
//printf("A%d ", a[siz - 1]);
return reqd(a, siz-1, sum);
}
else if(a[siz - 1] == sum && siz > 0)
{
printf("B%d ", a[siz - 1]);
return (1);
}
else if(a[siz - 1] < sum && siz > 0)
{
printf("C%d ", a[siz - 1]);
i = reqd(a, siz, sum - a[siz - 1]);
if(i <0 )
return reqd(a, siz-1, sum);
else return (1 + i);
}
else
printf("failed ");
return -1;
}
main()
{
int ar[] = {3,5,7,11}; // sorted array
int siz = 4; //size of above array
int sum=0,j=0;
scanf("%d", &sum);
j = reqd(ar, siz, sum);
printf("\n%d", j);
}
#include <iostream>
#include <string.h>
#include<limits.h>
using namespace std;
int change(int *coin, int size, int num){
int total[num + 1];
total[0] = 0;
for (int i = 1; i <= num; i++){
total[i] = INT_MAX;
for (int j = 0; coin[j] <= i && j < size; j++){
if (total[i - coin[j]] + 1 < total[i] )
total[i] = total[i - coin[j]]+ 1;
}
}
return total[num];
}
int main() {
int coin[3] = {1, 3, 5};
int k =11;
int size = sizeof(coin)/sizeof(coin[0]);
cout<<change(coin, size, k);
return 0;
}
I think this is simple Change problem, which can be solved by DP or recursion.
pseudo code for this will be....
Change(array, size, target) best_change[0] = 0 for c in target best_change[c] = infinite for i in size if c > array[i] best_change[c-array[i]] + 1 < best_change[c] best_change[c] = best_change[c- array[i]] + 1 return best_change[target]and array need not to be sorted....
- Aks July 10, 2012