Coin Change

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type

Given a value of x cents, and an infinite supply of coins of n denominations, followed by their denominations, find the least amount of coins required to make change for x.

Input Specification

Line 1: x, an integer between 1 and 10\,000.
Line 2: n, the number of different denominations.
Line 3 \dots 3+n: the denominations of the coins.

Output Specification

An integer, on a single line - the least coins required to make change for x.

Sample Input

24
4
12
13
5
6

Sample Output

2

Comments


  • 6
    John  commented on March 24, 2022, 1:46 p.m.

    My algorithm was wrong and yet I got 100% AC...?


  • 4
    Nils_Emmenegger  commented on June 17, 2021, 7:31 p.m.

    The maximum value of n is 86.


  • 3
    OneYearOld  commented on Dec. 11, 2020, 1:19 p.m.

    According to the problem author, it is always possible to make change for x.