CODEWITHSUNDEEP
algorithmcoin-change
Callum Woodward
Callum Woodward

Reputation: 5

Coin change algorithm

would just like to double check this code will not have any errors, mainly to do with the modulus operator I'm unsure about.

The question is:

Problem: Write an ACL algorithm that, given a cost of an item (less than or equal to one dollar), gives the number of 50 cent, 20 cent, 10 cent, 5 cent and 1 cent coins the buyer would receive if they handed over one dollar. You must minimise the number of coins in the change.

My solution is:

Algorithm coin_change
{
    int cost, change, fifty, twenty, ten, five, one;
    read(cost);
    change = 100 - cost;

    fifty = change / 50;
    change = change % 50;

    twenty = change / 20;
    change = change % 20;

    ten = change / 10;
    change = change % 10;

    five = change / 5;
    change = change % 5;

    one = change;

    print(fifty, twenty, ten, five, one);
}

Main thing I'm unsure about is for instance if the change is 93 cents, this will change to 43 cents, then down to 3 cents. Now question is will "change = change % 10" when change is 3 cents return change to equal 3 still? Hope that made sense.

Thanks in advance.

Upvotes: 0

Views: 1926

Answers (2)

lerenau
lerenau

Reputation: 193

Yes.

change = change % 10

this will still return 3 regardless of if change was initially 43 or 3.

Upvotes: 1

paxdiablo
paxdiablo

Reputation: 881563

3 modulo 10 will give you 3, by definition. It's the remainder left when you divide by the given number.

When you divide 3 by 10, you get 0 with a remainder of 3. So your algorithm is correct in that sense.

Generally, the only thing you need to worry about with modulo in computer languages is the treatment of negative numbers - some languages behave differently.

But you're not mucking about with negative numbers, so don't concern yourself with that.

Upvotes: 2

Related Questions