qwertyy123321's blog

By qwertyy123321, 6 years ago, In English

How to solve the coin change problem where you have to find the minimum no of coins required to make a sum N(given) from infinite no of coins of denominations given in an array of size M. for example denominations available {1,2,3,5,6} and N = 11 answer is 2(5+6). But here N can be given negative value and coins can also be negative values.

One solution is construction a graph with vertices: sum of all negative coins,...,-1,0,1,2,.... sum of all positive values. and having an edge between vertex i and j if (i-j) is one of the coins available. Then finding the shortest path using bfs on node number 0.

If M = 1e5 and each coin -1e5 < Ai < 1e5 this solution will fail. How to solve this for larger constraints?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints on N?