Coin Change: Minimum number of coins

Question

Problem:

You are given n types of coin denominations of values \$v(1) < v(2) < ... < v(n)\$ (all integers). Assume \$v(1) = 1\$, so you can always make change for any amount of money \$C\$. Give an algorithm which makes change for an amount of money \$C\$ with as few coins as possible.

---

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i,n,den[20],temp[20],min,min_idx, S, numcoins = 0;
    printf("Coin Change with min no. of coins\nEnter the total change you want: ");
    scanf("%d",&S);
    printf("Enter the no. of different denominations of coins available: ");
    scanf("%d",&n);
    printf("Enter the different denominations in ascending order: \n");
    for(i=0;i<n;i++)
        scanf("%d",&den[i]);
    while(S>0)
    {
        for(i=0;i<n;i++)
        temp[i] = S / den[i] ;
        /*calculate min from temp */
        min = temp[0] ;
        for(i=0;i<n;i++)
        {
            if(min > temp[i] && temp[i]!=0)
            {
                min = temp[i] ;
                min_idx = i ;
            }
        }
        numcoins += min ;
        S -= den[min_idx] * min ;
    }
    printf("min no of coins = %d" , numcoins) ;
    return 0;
}

In several solutions on the internet, I saw code using an array of the size of the total sum or value S, whereas I use only 2 arrays of size n, the number of different denominations available. That's why I was wondering whether my approach is correct or whether it's flawed.

Is it better or worse in terms of time complexity? Also, am I properly using dynamic programming principles in my code? Can it be made more efficient? The code ran correctly for several test cases.

I am sorry for poor code formatting and a not-so-clean code. It is a small code, so I hope it is understandable. My main concern is whether the code is dp or not, and if it can be improved for efficiency.

Answer 1

Bug

You code is currently too simplistic. All it does is make change from the highest denomination possible. It fails on the following input:

 Enter the total change you want: 6
 Enter the no. of different denominations of coins available: 3
 Enter the different denominations in ascending order:
 1 3 4
 min no of coins = 3

Your program thought the change should be: 4 1 1 but the best solution was actually 3 3.

Your program doesn't currently use any dynamic programming principles. In order to do so, you would need to keep an array holding the best number of coins per change amount. You could then iterate starting at 1 and build up to the total change requested.

Answer 2

Currently, your code is next to unreadable.

The variable names are too cryptic. Names like den and S don't tell anything about the context of the variable.

Please, use descriptive names.

---

You don't give space for your variables to breath. You crammed everything up and that makes it harder to read.

An example:

for(i=0;i<n;i++)
temp[i] = S / den[i] ;

Could be written as

for(i = 0; i < n; i++)
temp[i] = S / den[i];

---

Still on the same for, you forgot to indent it.

Indentation is important to check what belongs where. Code is read far more times than written. Improve it's readability.

---

Still beating on that same for, you should always have brackets around your statements. Remember the Apple SSL bug? Well, it may happen with you.

Try this instead:

for(i = 0; i < n; i++)
{
    temp[i] = S / den[i];
}

---

You should declare your variables as close as possible of when you will use them.

One example is this:

for(i = 0; i < n; i++)
{
    temp[i] = S / den[i];
}

I would do like this:

for(int i = 0; i < n; i++)
{
    temp[i] = S / den[i];
}

---

A few lines below, you have this:

min = temp[0] ;
for(i=0;i<n;i++)

You start by giving min the value of temp[0]. Why don't you start the loop at 1? You reduce 1 iteration!

Like this:

int min = temp[0];
for(int i = 1; i < n; i++)

This would speed-up your code by a very small bit, but it is important to notice.

And to squeeze a tiny bit of performance, you can change:

if(min > temp[i] && temp[i]!=0)

Into this:

if(temp[i]!=0 && min > temp[i])

Now you ask: Why? And the answer is because of shortcut evaluation. If temp[0] is false, it won't evaluate min > temp[i], because we know that it will be false as well.

This won't save much, but you shave some comparisons. Which is really good!

---

If you want, I can even eliminate that tiny loop I've refered before:

int min = S / den[0];
int min_idx = 0;
for(int i = 1; i < n; i++)
{
    int temp = S / den[i];
    if(temp!=0 && min > temp)
    {
        min = temp;
        min_idx = i;
    }
}

And so, you can eliminate the tiny for and the temp[20]. This was untested and may not work!

---

You trust too much in the user. You have no validation what-so-ever! I could say I have 5 coins and then only give 2 denomination in the wrong order. What would happen?

---

Also, how can I say that I have a 0.5€ coin? Or a 2€ coin? Would it be 50 and 200?

---

I'm really sorry if I said something that might not fit at 100%. I'm not 100% confortable with C. But I hope I've helped you.

Answer 3

Everything is in main. It's called main. It's not called everything.

You have written no functions here, but you should. Writing functions is a way of giving names to chunks of code that are independent, testable, and give a desired result for a given input (and do that in the same way every time). Plus, it goes a long way to making our code far more readable (which makes it less prone to bugs, and easier to fix when those bugs do crop-up because we've self-documented our code).

As with any problem, we treat it as an elephant and solve it one bite at a time. Let's look back the the plain English description of the problem:

You are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so you can always make change for any amount of money C. Give an algorithm which makes change for an amount of money C with as few coins as possible.

So, before we write any code, what are the bites we need to take?

1. Get the number of unique coin denominations.
2. Get the value of a coin denominations.
3. Repeat step two one per denomination entered.
4. Get an amount of money to make change for.
5. Calculate change.
6. Output change.

This is a quick, easy list to come up with before writing a single line of code. We also have some important words here.

• Get - an indication that we need input from the user.
• Repeat - an indication we need a loop.
• Calculate - an indication we need a function that will take input and return output
• Output - an indication that we need to print to the console

So from here, how do we need to put the pieces of the puzzle together?

Well, let's write some reusable code.

Tasks 1, 2, and 4 all require us to get input from the user. This can all be done with a single function. Something along the lines of this:

int getUserInput(const char * prompt) {
    // display prompt to user
    // get input from console
    // if input is valid int, return it
    // else display error message and start from beginning
}

So now, since we're passing the input in, we can reuse this function for tasks 1, 2, and 4:

int denominationCount = getUserInput("How many denominations are there?");

(And the same with different prompts for the other tasks.)

_{Ultimately, one might argue for an approach that continues to accept denominations from the user until they indicate they don't want any more denominations.}

So, we've solved half of our tasks with one simple, easy function. Let's look at task #3. Task 3 will require, as a sub-task, task 2, so we know we're looking at a function that will end up calling the above function we just wrote, right? And what should it return? Sounds like it should return an array. Or perhaps it should take an array by reference and fill it?

void getDenominations(int *denominations, int denominationCount) {
    for (int i = 0; i < denominationCount; ++i) {
        denominations[i] = getUserInput("Enter the next denomination:");
    }
}

Of course, you probably want to put a little more effort in than this. I'm just outlining a possible guideline to start you on the right foot. You want a more dynamic prompt message (indicating which number they're on) and you probably want some validation to make sure they're not entering duplicate denominations.

Now we've resolved tasks 1 through 4. We need task 5, which is the big calculate one. I'm not going to get into the specifics of the actual calculation, but suffice to say, this should simply be a function that returns the result in some way (probably an array of denominations).

And then the final step is simply outputting the result to the console.

So our main function is no longer everything, but is instead a series of function calls.