# Minimum number of coins problem using dynamic programming - follow up

I previously posted a code here. It turns out that the code is not following the correct dynamic programming principles and instead it was based on a greedy approach. Hence, I started again, keeping in mind helpful guidelines from here and here. I would now like to know if my code is efficient, or if it can be further optimized in terms of time and space complexity.

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

int i , no_of_denominations , denominations [ 10000 ] , total_cost , cost [ 10000 ] ;

int min ( int idx )
{
int min_cost = 99999 , j ;
cost [ 0 ] = 0 ;
for ( j = 0 ; j < no_of_denominations ; j++ )
{
if( ( i >= denominations [ j ] ) && ( min_cost > cost [ i - denominations [ j ] ] ) )
{
min_cost = cost [ i - denominations [ j ] ] ;
}
}
return min_cost ;
}

void input()
{
printf ( "Coin Change with min no. of coins\nEnter the total change you want: " ) ;
scanf ( "%d" , &total_cost ) ;

printf ( "Enter the no. of different denominations of coins available: " ) ;
scanf ( "%d" , &no_of_denominations ) ;

printf ( "Enter the different denominations in ascending order: \n" ) ;
for ( i = 0 ; i < no_of_denominations ; i++ )
{
scanf ( "%d" , &denominations [ i ] ) ;
}
}

void calc_print ()
{
for ( i = 1 ; i <= total_cost ; i++ )
{
cost [ i ] = 1 + min ( i ) ;
}

printf ( "min no of coins = %d" , cost [ total_cost ] ) ;
}

int main()
{
input () ;
calc_print () ;
return 0;
}

• I advise you to add - follow-up at the end of your title. This way, you will avoid people looking at the title and say it is a duplicate – Ismael Miguel Aug 14 '15 at 11:45
• Since performance of the algorithm is $O(nm)$, $n$ being the amount and $m$ being the number of coin denominations, for most inputs it will probably not affect the running time to sort the denominations, an $O(m \log m)$ operation, so that you can break early of loops in your min function, making things potentially a little faster overall. – Jaime Aug 14 '15 at 13:58
• I've edited the question, since you forgot to add the language tag. That tag is required. If I tagged it incorrectly, please rectify it – Ismael Miguel Aug 14 '15 at 14:10
• @Jaime : Thanks for the tip! Will definitely incorporate it in my code. – CyberLingo Aug 15 '15 at 3:13

I advised you that it is called main and not everything, and you did a good job of moving code out of main. Now main looks a lot closer to what I'd expect to see.

But, we still have functions that are doing too much. Plus, we've made a bad problem worse. We've replaced doing everything in the main function with global variables. And we don't want to do that.

One indication that we have functions that are doing too much is that our functions don't have very great names and there's not a good name to give to them.

For example, void input(). It's not very clear what exactly this function does (from name alone), and we can't really give it a more clear name without it being miles long (and filled with ands... "and" and "or" in function names is generally a code smell). From the name alone, we'd guess that this function gets input from the user. But what does it do with that input? Who knows? Because this returns void and it doesn't take anything by reference to return either.

So let me repeat the method from earlier more clearly (this you can and should copy-and-paste this exactly and use it):

int getUserInput(const char * prompt) {
int input;
printf(prompt);
scanf("%d", input);
return input;
}


Do not mistake this. You're repeatedly getting integer input from the user. This is a clear indication that you should have a function for doing this. If you don't have this in your next post, you're doing something very wrong.

The section in which we gather inputs from the user should look basically exactly like this:

int denominationCount = getUserInput("How many different denominations? ");
for (int i = 0; i < denominationCount; ++i) {
denominations[i] = getUserInput("Enter the next denomination: ");
}
int makingChangeFor = getUserInput("How much are we making change for? ");


And now you've got all the values for which to do the calculation. You can feed them to the function that does the calculation and get an output from that. And you don't need the global variables.

Until all of your functions that are accessing the global variables are both taking and returning arguments, you shouldn't be comfortable using the global variables (as a rough guideline). Global variables are almost always unnecessary. Global variables are the path to rats nests, madness, and lunacy.

• I was always confused whether global variables are good or not. Thanks for clearing up my doubts! – CyberLingo Aug 15 '15 at 3:09

The first thing I can say is that you didn't listened to me.

Look at this block:

for ( i = 0 ; i < no_of_denominations ; i++ )
{
scanf ( "%d" , &denominations [ i ] ) ;
}


What did I say? Declare variables as close to where you will use them as possible.

You should have this:

for ( int i = 0 ; i < no_of_denominations ; i++ )
{
scanf ( "%d" , &denominations [ i ] ) ;
}


See? It doesn't kill you and your compiler will be happy!

Still, there is no validation of the data. And there's no way to pick 0.5€ (50 cents).

You should look into that.

But now you have a new problem: too much whitespace!

Look at this:

int min_cost = 99999 , j ;
cost [ 0 ] = 0 ;
for ( j = 0 ; j < no_of_denominations ; j++ )
{
if( ( i >= denominations [ j ] ) && ( min_cost > cost [ i - denominations [ j ] ] ) )
{
min_cost = cost [ i - denominations [ j ] ] ;
}
}


How can I read this? Where is everything closing and opening?

You should write it as this:

int min_cost = 99999;
cost[0] = 0;
for (int j = 0; j < no_of_denominations; j++)
{
if ( (i >= denominations[j]) && (min_cost > cost[i - denominations[j]]) )
{
min_cost = cost [i - denominations[j]];
}
}


At least I find it easier to read. Way easier!

Other than that, it seems pretty much day and night, comparing to the old code.

• Thanks and sorry! I thought that since i was used in all functions, so I would declare it once only. Starting the loop at 1 gives me wrong answer for some test cases. – CyberLingo Aug 14 '15 at 12:10
• @CyberLingo You can declare once, but don't do that. Compilers won't optimize it and you will be "bleeding" local data outside. Imagine that now you change your code to run the loop with i, and inside that loop you have another loop that uses i too. You end up doing some nasty stuff with loops running all weird. And about starting in 1, do you want me to delete that? – Ismael Miguel Aug 14 '15 at 13:11
• Thanks, got it! About loop starting with 1, you can delete it if you like, because it made sense in my previous code, but not in this code – CyberLingo Aug 14 '15 at 13:37
• Declaring the variable inside the for loop may not be valid C, Microsoft's Visual C is notorious for accepting only C89 syntax. – Jaime Aug 14 '15 at 13:48
• Also, if looking for a consistent set of formatting rules, Google's C++ style guide is a good starting point. I for one still see too much whitespace and unnecessary parenthesis in that corrected if statement. – Jaime Aug 14 '15 at 13:53