# PROBLEM LINK

# DIFFICULTY

CAKEWALK

# PREREQUISITES

# PROBLEM

You are given **N** banknotes `{ A`

_{1}`, A`

_{2} `..., A`

_{N}`}`

given by a customer to buy sweets. One sweet costs X units.

For the number of sweets the customer wants to buy, **all** the banknotes are supposed to be used, that is, you shouldn’t be able to buy that many sweets by discarding any banknote.

What is the largest number of sweets does the customer want to buy?

# QUICK EXPLANATION

Check whether the smallest value can be ignored. If it can, the answer is -1. Otherwise, the answer is the maximum number of sweets the customer **can** buy.

# EXPLANATION

Let, `S =`

∑_{(i = 1 to N)}`A`

_{i}

Obviously, the customer can buy, at max `V = floor(S / X)`

sweets.

- It should be clear from the problem statement that you will always give the customer
`V`

sweets- Since, the statement asks you to return the maximum number of sweets he can buy by using all the banknotes.

- All that remains to check is, whether you must use all the banknotes to buy
`V`

sweets or not. - I.E. you need to check if V sweets can be bought by ignoring at least one of the banknotes, which results in the customer being “Inadequate”.
- If the customer is inadequate, you must print -1.
- Otherwise, the answer will be V.

To buy `V`

sweets, you must use at least `V * X`

amount of money.

Let, `R = S - (V * X) = S % X`

, where `%`

is the remainder (or modulo) operation.

**Lemma**

If there is no banknote given whose value is less than `R`

, then the customer is adequate.

Also, if there is a banknote whose value is less than `R`

, then the customer is inadequate.

**Proof**

Let us say you could ignore a banknote `b`

.

That means,

`floor((S - b) / X) = V`

`floor((S - b) / X) = (S - R) / X`

`((S - b) / X) - (((S - b) % X) / X) = (S - R) / X`

```
R - b = (S - b) % X
```

Now, if `b > R`

then the above expression is absurd; since `R - b`

is negative and `(S - b) % X`

is positive.

However, if `b <= R`

then above expression is always true.

Thus, the necessary and sufficient condition for the customer to be adequate is that there is no banknote whose value is less tan or equal to S % X. The code to solve the problem will look like

M = minimum(x: x = A[i], for all i = 1 to N) S = sum(x: x = A[i], for all i = 1 to N) R = S % X if R < M print S / X else print -1

# SETTERS SOLUTION

Can be found here

# TESTERS SOLUTION

Can be found here