Create a gist now

Instantly share code, notes, and snippets.

Cash Register Problem

Cash Register Problem

Write a program that calculates the optimal number of coins from a set of given denominations to produce a given amount of currency. The correct answer should be the lowest number of total coins given.


The first line:

k d1 d2 ... dk
  • where k in an integer that represents the number of coin denominations to follow on the same line.
  • where d1 ... dk are integers representing the coin denominations in cents.

The second line:

  • where n is the number of test cases to follow.

The following n lines:

  • where a is an integer that represents the total amount of change to make in cents.


For each test case, output one line:

d1 d2 d3 ...
  • where d1 ... represents one coin of any of the given denominations provided by the input.



4 1 5 10 25			# four coins: 1, 5, 10 and 25 cents
3 					# three test cases
123 				# 1.23 dollars
7 					# 0.07 dollars
39 					# 0.39 dollars


25 25 25 25 10 10 1 1 1
5 1 1
25 10 1 1 1 1

Test Cases


  • Yes, this is a well known weakly NP-hard problem.
  • This means there are a few pseudo-polynomial time solutions to this problem
  • See if you can figure one of them out before you research the problem and its analogs.

This comment has been minimized.

Show comment
Hide comment
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment