Coin Denomination Problem

2008-02-27T08:45:00.000-08:00

The coin denomination problem (also known as the coin changing problem) is usually given as a demonstration for the uses of dynamic programming. It is also known to have been given as an interview question by big companies such as Google and Microsoft.

The coin denomination problem is as follows: given a number which needs to be broken down into change (such as 24$), and a set of coins (or bills) or different values (such as 10$, 8$, 5$, 2$, and 1$ bills) what is the minimum number of bills needed which will add up to make the number.

Since I am currently in the interview process with Google, I was searching for the type of questions on the internet, which is where I was first introduced to this problem. The author of one post I found (here) who described his own phone interview with Google, said that the interviewer had asked him to give a solution to this problem, which he said he had stated in another blog post (here).

But the solution that I had found was not recursive, the way it should be to demonstrate the use of dynamic programming in this case. I went ahead and wrote my own solution to this problem, in Python, a language I love (also freely available for windows).

The code:

def CoinDenomination(value,coinArray):
  if value == 0:
      return [0,[]]
    
  if value < 0:
      return [100000000,[]]
    
  minval = 100000
  minind = len(coinArray)+1

  for i in range(len(coinArray)):
      retVal = CheckLeast(value-coinArray[i],coinArray)
      if temp[0] < minval:
          minval = retVal[0]
          minind = i
          coins = retVal[1]
  coins.append(coinArray[minind])
  return [1 + minval,coins]


if __name__=="__main__":
  retVal = CoinDenomination(24,[10,8,5,2,1])
  print "Number of coins:\t",retVal[0]
  print "Coins:\t\t\t",retVal[1]

It can be shown that this solution will always produce the optimal result (the least number of coins) whereas the greedy algorithm will always be faster than this solution. It is meant to demonstrate the power of dynamic programming and is a good exercise to try.

Please feel free to publish your comments and questions below, I would be happy to help clarifying this if I can.

Enjoy!

My Google Interview

Coin Denomination Problem