## Coin Change

View as PDF

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

Author:
Problem type

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

#### Input Specification

Line : , an integer between and .
Line : , the number of different denominations.
Line : the denominations of the coins.

#### Output Specification

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

#### Sample Input

24
4
12
13
5
6

#### Sample Output

2

## Comments

• 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?

• commented on Dec. 3, 2023, 10:07 p.m. edit 2

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.

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

Thank you!

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

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

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

The maximum value of is .

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

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