Coin Change

View as PDF

Submit solution

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

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


Sample Output



  • 0
    Viv_CCGS  commented on Dec. 3, 2023, 3:18 a.m.

    When I submit in PyPy3, I get IR (failed initialising), but the same code runs in Python 3, though I do get a TLE. What is happening?

    • 0
      volcano  commented on Dec. 3, 2023, 10:07 p.m. edited

      PyPy is faster than CPython, but uses more memory. Since the memory limit is 16MB, PyPy3 is not suitable (or necessary) for this problem.

      Your TLE solution is recursive, and is slower than your iterative AC solution.

      • 0
        Viv_CCGS  commented on Dec. 4, 2023, 11:28 a.m.

        Thank you!

  • 7
    John  commented on March 24, 2022, 5:46 p.m.

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

  • 6
    Nils_Emmenegger  commented on June 17, 2021, 11:31 p.m.

    The maximum value of n is 86.

  • 4
    OneYearOld  commented on Dec. 11, 2020, 6:19 p.m.

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