Problem
[Question asked during online Test.]
Given a list of 'N' coins, their values being in an array A[],
return the minimum number of coins required to sum to 'S' (you can use as many coins you want).
If it's not possible to sum to 'S', return -1
Sample Test Cases:
Input :
Coin denominations: { 1,3,5 }
Required sum (S): 11
Output :
3
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find changes
Created Date : 19-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <iterator>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
void FindChanges(int sum, vector<int>& coins, vector<int>& changes, int& minNum, int index, bool& found)
{
if(sum == 0){
found = true;
if(changes.size() <= minNum){
minNum = changes.size();
cout << "The changes " << endl;
copy(changes.begin(), changes.end(), ostream_iterator<int>(cout, " "));
cout << endl;
return;
}
}
else if(sum < 0){
return;
}
if(sum < coins.at(coins.size() - 1)){
return;
}
for(int i = index; i < coins.size(); ++i){
if(sum >= coins.at(i)){
changes.push_back(coins.at(i));
FindChanges(sum - coins.at(i), coins, changes, minNum, i, found);
changes.pop_back();
}
}
}
int main(int argc, char* argv[])
{
vector<int> coins;
coins.push_back(2);
coins.push_back(4);
coins.push_back(9);
vector<int> changes;
int sum(101);
bool found(false);
// make sure coin is sorted in descending order
sort(coins.begin(), coins.end(), [](int i, int j){return i > j;});
cout << "The coins in descending order " << endl;
copy(coins.begin(), coins.end(), ostream_iterator<int>(cout, " "));
cout << endl;
int minNum = sum / coins.at(coins.size() - 1) + 1;
FindChanges(sum, coins, changes, minNum, 0, found);
cout << "The sum is : " << sum << endl;
if(found){
cout << "The minimum num is " << minNum << endl;
}
else{
cout << "Cannot find a solution" << endl;
}
cout << "----------------------------------------------" << endl;
for(int i = 1; i < 50; i++){
coins.clear();
coins.resize(0);
changes.clear();
changes.resize(0);
int len = rand() % 10 + 1;
set<int> s;
for(int j = 0; j < len; ++j){
s.insert(rand() % 30 + 1);
}
coins.insert(coins.begin(), s.begin(), s.end());
sort(coins.begin(), coins.end(), [](int i, int j){return i > j;});
cout << "The coins in descending order " << endl;
copy(coins.begin(), coins.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "The sum is : " << i << endl;
minNum = i / coins.at(coins.size() - 1) + 1;
found = false;
FindChanges(i, coins, changes, minNum, 0, found);
if(found){
cout << "The minimum num is " << minNum << endl;
}
else{
cout << "Cannot find a solution" << endl;
}
cout << "----------------------------------------------" << endl;
}
return 0;
}
Output
The coins in descending order
9 4 2
The changes
9 9 9 9 9 9 9 9 9 9 9 2
The sum is : 101
The minimum num is 12
----------------------------------------------
The coins in descending order
18 5
The sum is : 1
Cannot find a solution
----------------------------------------------
The coins in descending order
30
The sum is : 2
Cannot find a solution
----------------------------------------------
The coins in descending order
23 19 15 6
The sum is : 3
Cannot find a solution
----------------------------------------------
The coins in descending order
28 26 12 3 2
The sum is : 4
The changes
2 2
The minimum num is 2
----------------------------------------------
The coins in descending order
25 23 22 7 4 3
The sum is : 5
Cannot find a solution
----------------------------------------------
The coins in descending order
19 18 12 10 9 7 6
The sum is : 6
The changes
6
The minimum num is 1
----------------------------------------------
The coins in descending order
26 20 18
The sum is : 7
Cannot find a solution
----------------------------------------------
The coins in descending order
24 22 4 3
The sum is : 8
The changes
4 4
The minimum num is 2
----------------------------------------------
The coins in descending order
29 24 22 18 2
The sum is : 9
Cannot find a solution
----------------------------------------------
The coins in descending order
28 24 23 20
The sum is : 10
Cannot find a solution
----------------------------------------------
The coins in descending order
29 20
The sum is : 11
Cannot find a solution
----------------------------------------------
The coins in descending order
21 19 17 13 11 6 3
The sum is : 12
The changes
6 6
The minimum num is 2
----------------------------------------------
The coins in descending order
29 27 21 16 10
The sum is : 13
Cannot find a solution
----------------------------------------------
The coins in descending order
21
The sum is : 14
Cannot find a solution
----------------------------------------------
The coins in descending order
25 24 22 10 9 5 4
The sum is : 15
The changes
10 5
The minimum num is 2
----------------------------------------------
The coins in descending order
29 27 25 21 17 12 10
The sum is : 16
Cannot find a solution
----------------------------------------------
The coins in descending order
29 18 14 13 12 10 9
The sum is : 17
Cannot find a solution
----------------------------------------------
The coins in descending order
25 20 19 6
The sum is : 18
The changes
6 6 6
The minimum num is 3
----------------------------------------------
The coins in descending order
28
The sum is : 19
Cannot find a solution
----------------------------------------------
The coins in descending order
24 23 15 12 7 6 1
The sum is : 20
The changes
15 1 1 1 1 1
The changes
12 7 1
The changes
7 7 6
The minimum num is 3
----------------------------------------------
The coins in descending order
28 18 17 13 12 7 6 4 1
The sum is : 21
The changes
18 1 1 1
The changes
17 4
The minimum num is 2
----------------------------------------------
The coins in descending order
23 22 21 12 11 5
The sum is : 22
The changes
22
The minimum num is 1
----------------------------------------------
The coins in descending order
28 17 12 11 8
The sum is : 23
The changes
12 11
The minimum num is 2
----------------------------------------------
The coins in descending order
30 20 18 9 8 6 4
The sum is : 24
The changes
20 4
The changes
18 6
The minimum num is 2
----------------------------------------------
The coins in descending order
19 3
The sum is : 25
The changes
19 3 3
The minimum num is 3
----------------------------------------------
The coins in descending order
27 13 12 11 9 4 1
The sum is : 26
The changes
13 13
The minimum num is 2
----------------------------------------------
The coins in descending order
30 25 18 11 9 4
The sum is : 27
The changes
18 9
The minimum num is 2
----------------------------------------------
The coins in descending order
27 22 21 15 3 2
The sum is : 28
The changes
22 3 3
The minimum num is 3
----------------------------------------------
The coins in descending order
7
The sum is : 29
Cannot find a solution
----------------------------------------------
The coins in descending order
19 10
The sum is : 30
The changes
10 10 10
The minimum num is 3
----------------------------------------------
The coins in descending order
25 24 20 19 9 5 2 1
The sum is : 31
The changes
25 5 1
The changes
24 5 2
The changes
20 9 2
The minimum num is 3
----------------------------------------------
The coins in descending order
22 19 18 14 9 1
The sum is : 32
The changes
22 9 1
The changes
18 14
The minimum num is 2
----------------------------------------------
The coins in descending order
30 27 22 21 14 6 5
The sum is : 33
The changes
27 6
The minimum num is 2
----------------------------------------------
The coins in descending order
30 29 27 25 20 16 15 4 3
The sum is : 34
The changes
30 4
The minimum num is 2
----------------------------------------------
The coins in descending order
28 24 14 5 4
The sum is : 35
The changes
14 5 4 4 4 4
The minimum num is 6
----------------------------------------------
The coins in descending order
30 27 19 12 9 1
The sum is : 36
The changes
30 1 1 1 1 1 1
The changes
27 9
The minimum num is 2
----------------------------------------------
The coins in descending order
30 29 23 18 13 11 9 8
The sum is : 37
The changes
29 8
The minimum num is 2
----------------------------------------------
The coins in descending order
29 16
The sum is : 38
Cannot find a solution
----------------------------------------------
The coins in descending order
27 25 22 19 16 3
The sum is : 39
The changes
27 3 3 3 3
The minimum num is 5
----------------------------------------------
The coins in descending order
27 24 6
The sum is : 40
Cannot find a solution
----------------------------------------------
The coins in descending order
30 25 22 19 18 13 12 7 3 2
The sum is : 41
The changes
30 7 2 2
The changes
25 13 3
The changes
22 19
The minimum num is 2
----------------------------------------------
The coins in descending order
30 23 21 6 4 3
The sum is : 42
The changes
30 6 6
The changes
21 21
The minimum num is 2
----------------------------------------------
The coins in descending order
26 23 22 19 16 14 12 10 3
The sum is : 43
The changes
26 14 3
The changes
23 10 10
The changes
19 14 10
The changes
19 12 12
The minimum num is 3
----------------------------------------------
The coins in descending order
30 28 25 23 17 12 3
The sum is : 44
The changes
23 12 3 3 3
The changes
17 12 12 3
The minimum num is 4
----------------------------------------------
The coins in descending order
29 26 20 15 13 10 6
The sum is : 45
The changes
29 10 6
The changes
26 13 6
The changes
20 15 10
The changes
15 15 15
The minimum num is 3
----------------------------------------------
The coins in descending order
26 3
The sum is : 46
Cannot find a solution
----------------------------------------------
The coins in descending order
29
The sum is : 47
Cannot find a solution
----------------------------------------------
The coins in descending order
30 20 17 4
The sum is : 48
The changes
20 20 4 4
The minimum num is 4
----------------------------------------------
The coins in descending order
28 20 14 8 7 6
The sum is : 49
The changes
28 14 7
The minimum num is 3
----------------------------------------------
Press any key to continue . . .