Task 4: Coins

Problem to solve

When a customer pays more than an item costs, a cashier returns the difference as change. The cashier should use the fewest coins possible.

In a file named coins.c inside a folder named coins, implement a C program that asks for an amount of change in Tajikistani dirams and prints the minimum number of coins needed.

For example:

$ ./coins
Change owed (dirams): 50
1

The program must work for any non-negative amount that can be made with the available coins:

$ ./coins
Change owed (dirams): 830
4

Coin values

One somoni equals 100 dirams. Use these coin values:

• 5 somoni (500 dirams)
• 3 somoni (300 dirams)
• 1 somoni (100 dirams)
• 50 dirams
• 20 dirams
• 10 dirams

Greedy algorithm

A greedy algorithm chooses the best immediate option at each step. For this coin system, repeatedly choosing the largest coin that does not exceed the remaining amount produces the minimum number of coins.

For example, the largest coin that fits into 830 dirams is a 5-somoni coin. After using it, 330 dirams remain. The next choices are a 3-somoni coin, a 20-diram coin, and a 10-diram coin. Therefore, 830 dirams requires four coins.

Requirements

• Prompt the user with Change owed (dirams):.
• Read the amount as an int using scanf and %d.
• Accept 0 or a positive integer divisible by 10.
• Re-prompt when the amount is negative.
• Re-prompt when the amount is not divisible by 10, because the smallest available coin is 10 dirams.
• Re-prompt when the input is not an integer.
• Calculate the minimum number of coins using the values listed above.
• Print only the final number of coins, followed by a new line.

Starter code

#include <stdio.h>

int main(void)
{
    int dirams;

    // Read a valid, non-negative amount of change.

    // Calculate the minimum number of coins.

    // Print the result.
}

Input hint

scanf returns 1 when it successfully reads one integer with %d. Check that return value before using dirams.

If scanf cannot read an integer, discard the invalid characters from the input line before prompting again. Otherwise, the same invalid input will remain waiting for the next call to scanf.

Algorithm hint

Work from the largest coin to the smallest:

1. Determine how many 5-somoni coins fit and subtract their value.
2. Repeat for 3-somoni and 1-somoni coins.
3. Repeat for 50-, 20-, and 10-diram coins.
4. Add the numbers of coins used.

Integer division and the remainder operator (%) can make these calculations shorter.

Compile and test

From the coins folder, run:

cc coins.c -o coins
./coins

If your system provides gcc instead of cc, use gcc coins.c -o coins.

Check these cases:

Change in dirams	Minimum coins
0	0
10	1
20	1
30	2
50	1
70	2
100	1
300	1
500	1
600	2
800	2
830	4

Also enter a negative number, a value not divisible by 10, and a non-integer value to confirm that the program prompts again.

Continue with Task 5: Credit.