Task: ATM

Question

There are N banknotes of various denominations a1, a2, ..., aN at the ATM. The client wants to receive the amount in K UAH. It is necessary to determine by which the minimum number of bills can give this amount.

It is believed that the ATM has an unlimited number of notes of each denomination.

Input data
The first line is the number N - the number of denominations.

The second line - denominations - integers a1, a2, ..., aN, separated by spaces.

The third line is the amount K that the client wants to receive.

All numbers are integers and range from 1 to 100,000.

Result Format
The number of banknotes that an ATM will issue.

Example
Input data
2
100 500
700

Work result
3

Here is my code:

https://code.sololearn.com/c2r2RarR6hb3/?ref=app

But it is not ideal if you enter:
3
500 42 3
543
then it will output -1, but it should 25. How should I implement the code so that it iterates over such and similar cases?

Answer 1

700 = (1) x 500 + (2) x 100
(1) + (2) = 3

Is this how the calculation works?
How come calculation for 543 results in 25? I didn't understand.

Answer 2

Ipang My code calculates that for the sum of UAH 543, an ATM with denominations of 500, 42, 3 - cannot issue UAH 543 - ((1) * 500 + (1) * 42 = 542, 543! = 542) but this is not true because can be done so - (12) * 42 + (13) * 3 = 543.

Answer 3

Thank you for explanation Alexander 👍