coin smallest

[leo2008]

I am trying to find the amount here.
Input

The first line of input contains an integer M, the number of coins in bank.
The second line of input contains M integers: coin1, coin2... coinN. coini represents ith coin.

Output
Print smallest possible amount of cash that you will not be able to pay in super market.

int solution(int count_coin, int coin[count_coin])
{
        float coin1=0.50,total=0.0;
	int ncoins;
	printf("Number of 50 coins : ");
	scanf("%d",&ncoins);
	total += (ncoins * coin1);
	printf("** %.2f **",total);
        return;
}

[jonnin]

this is not well stated.
does something here indicate the value of the coins? eg dime vs penny?
does the supermarket need exact change?
or are you just trying to find out how much money you have such that you can't spend more than you have?

the whole thing reads like a bad contest site ... if chef has 10 bananas and 3 oranges, how many strawberry cakes can he make?

[lastchance]

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
using namespace std;

istringstream test( "7\n"
                    "1 2 2 5 10 10 50\n" );

int solution( const vector<int> &coins )
{
   set<int> allSums;
   for ( int c : coins )
   {
      set<int> current = allSums;
      allSums.insert( c );
      for ( int old : current ) allSums.insert( old + c );
   }

   int n = 0;
   for ( int s : allSums )
   {
      n++;
      if ( s != n ) return n;          // Find first positive integer not in allSums
   }
   return n + 1;
}

int main()
{
// istream &in = cin;
   istream &in = test;

   int M;
   in >> M;
   vector<int> coins( M );
   for ( int i = 0; i < M; i++ ) in >> coins[i];
   cout << solution( coins ) << '\n';
}

31

[leo2008]

I have a bank with M coins in it. The coin values may be different. So to buy a gift for my friends b'day, I break the bank. But the local super market does not have change, so I need to identify smallest possible amount of cash that I will not be able to pay in super market market. I am trying to find the amount here.

[jonnin]

ah. Much better explained!

if the coins were standard USA$ types, then you could have these values for them
1 P
5 N
10 D
25 Q
50 F
100 $

and, you have a total, from the above code, of how much actual money you have.
So for sure, you cannot buy something more than your total. That is your starting point answer.
But, if you find an item worth 1 (P) and your smallest coin is a N, then you can't buy it if you want change back (if you are willing to accept losing money due to lack of change, that is an uninteresting problem, its 1+total).

now it gets interesting.
the question, really, is what is the first number in 1 to T (t being your total) that you can't make with the coins you have.
There is probably a much better way to do this. I will leave that for you to play with.

Lets look at my 'early in the morning just looked at this for real' idea:
if you have 3P and 10 of everything else in your bank, you cannot make 4.
if you had 2P and 10 of everything else, you can't make 3 or 4.
why? because the next coin value is a 5. so unless you have at least 5-1 value in the previous coins, you can't make that number!
ok, but if you have 4P or more and some N, what is next?
you need at least 1 N and 4P to make everything from 1 to 9, one less than the next coin (D).
if you have 0N, then you need 9P. (it may be easier to swap 5p to 1N to get to a known state depending on how you code it).
and then you do 24 and so on up the chain. Note that if a coin is missing (say you have 0D) then you just move on as if that coin type does not exist -- you have to check 1 to 24 instead of 1-9 above (you must make 1 to 24 from only P and N). If you also have 0Q, then you have to make 1-50 with P and N. And so on.
its complicated, but I think if you go down that path you can find a way to figure out what you cannot generate without resorting to brute force.

[leo2008]

Hi jonnin

do you mean to use a binary search here or iterate through all the possible combinations or something like the below?

int coinSolution(vector<int>& coins, int cashamount) 
    vector<int> K(cashamount+1, cashamount+1);
    K[0] = 0;
    for (int coin : coins) {
        for (int i = coin; i <= cashamount; i++) {
            K[i] = min(K[i], K[i - coin] + 1);
        }
    }
    return K[cashamount] > cashamount ? -1 : K[cashamount];
}

[jonnin]

binary search what? You need a sorted list and something to look for?
I specifically said the goal was to avoid every possible combo...
the idea is to find the first 'gap' from cost of 1 unit to your total value.
if your smallest coin is worth 5 units, you can't pay 1,2,3,4 ... build off that idea, as above.

[leo2008]

I need to identify smallest possible amount of cash that I will not be able to pay in super market market. Yes goal is to avoid all combos.

[lastchance]

What was wrong with the solution given earlier?
https://www.cplusplus.com/forum/general/281690/#msg1218749

[jonnin]

nothing.
its a form of brute force with early exit, and I believe there is a way to do less though.
you have 10 points of change that covers 1-10 values. you add 10. you now know that 1-20 are valid. you add 10, you now know that 1-30 are valid. you add 50... can't make 31. There should, in other words, be a way to avoid some of the iteration.
Is it worth it? No, just a theoretical 'could be better' observation. What you did will solve it up to a ginormous, large bank vault sized number of coins and total in under a second.

[lastchance]

If you are prepared to sort the coins first then you can exit the algorithm early when the addition of the next coin leaves a sum-gap (the 50 coin in the example below).

But if you have a lot of small-value coins that won't help you much.

#include <set>
#include <algorithm>
using namespace std;

istringstream test( "7\n"
                    "1 2 2 5 10 10 50\n" );

int solution( const vector<int> &coins )      // coins should be sorted first
{
   set<int> allSums;
   for ( int c : coins )
   {
      if ( c > allSums.size() + 1 ) break;    // early exit if the addition of this coin leaves a gap
      cout << "Considering coin " << c << '\n';
      set<int> current = allSums;
      allSums.insert( c );
      for ( int old : current ) allSums.insert( old + c );
   }

   int n = 0;
   for ( int s : allSums )
   {
      n++;
      if ( s != n ) return n;                 // find first positive integer not in allSums
   }
   return n + 1;
}

int main()
{
// istream &in = cin;
   istream &in = test;

   int M;
   in >> M;
   vector<int> coins( M );
   for ( int i = 0; i < M; i++ ) in >> coins[i];
   sort( coins.begin(), coins.end() );
   cout << "Smallest no-change amount is " << solution( coins ) << '\n';
}

Considering coin 1
Considering coin 2
Considering coin 2
Considering coin 5
Considering coin 10
Considering coin 10
Smallest no-change amount is 31

[jonnin]

exactly :)

[leo2008]

Below is my code

class coinSolution {
public:
    int coinSolution(vector<int>& coins, int cashamount) {
        vector<int> D(cashamount+1, MAX_INT-1);
        int n = coins.size(), i, j;
        D[0] = 0;
        for(i=1; i<=cashamount; i++)
        {
            for(j=0; j<n; j++)
            {
                if(i-coins[j]>=0)
                    D[i] = min(D[i], D[i-coins[j]]+1);
            }
        }
        
        if(D[cashamount] == MAX_INT-1)
            return -1;
        else
            return D[cashamount];
    }
};

My Input:

[1,2,5]
11

My Output:

3

[lastchance]

My Input:

[1,2,5]
11

My Output:

3

Your input doesn't match the form given in the original post.
No idea what 11 is supposed to represent.
Surely 1+2=3 ??


I don't believe for one moment that is "your" code ... which actually seems to be solving a different problem (5+5+1=11; that's 3 coins minimum).

[leo2008]

I was checking with some random test case here, but it seems there is some issue with my logic. Please ignore my inputs mentioned earlier. I need to identify smallest possible amount of cash here.