Exchange

Problem Statement

* WARNING: Do not leave the competition room while you are competing. If you have a question, use "admins: question" in the chat area. *

John owes Mary some money, and Mary wants John to pay her back right this instant! However, in order for John to pay the exact debt (of course he doesn't want to pay more than he owes, and Mary doesn't want him to pay less), coins might have to be passed both ways for the debt to be settled. Given the coins John and Mary has, you should determine the minimum number of coins that need to exchange hands in order for the debt to be settled.

For instance, assume John has three pennies (1 cent each), two dimes (10 cents each) and one half-dollar (50 cents), Mary has two pennies and one quarter (25 cents) and that the debt is 23 cents. One way for John to repay his debt is to give Mary three pennies and two dimes (+1+1+1+10+10=23), resulting in 5 coins exchanging hands. A better way is to give her the half-dollar while Mary gives him two pennies and a quarter (+50-1-1-25=23), resulting in only 4 coins exchanging hands.

Create a class Exchange which contains the method min which takes as input a int[] johnCoins, John's coins, a int[] maryCoins, Mary's coins, a int debt, how much John owes Mary (in cents), and returns the minimum number of coins that need to exchange hands in order for John to pay back his debt exactly. If there is no solution, return -1.

Definition

Class:: Exchange
Method:: min
Parameters:: int[], int[], int
Returns:: int
Method signature:: int min(int[] johnCoins, int[] maryCoins, int debt)
(be sure your method is public)

Notes

If John and Mary can't settle the debt exactly, return -1 (see example 1).

Constraints

johnCoins will contain between 0 and 50 elements, inclusive.
maryCoins, will contain between 0 and 50 elements, inclusive.
Each element in johnCoins will be either 1, 5, 10, 25 or 50.
Each element in maryCoins will be either 1, 5, 10, 25 or 50.
debt will be between 1 and 2500, inclusive.

Examples

```
{1,1,1,10,10,50}
```
```
{1,1,25}
```
```
23
```
```
Returns: 4
```
This is the example mentioned above.
```
{1,5,10,25,50}
```
```
{1,5,10,25,50}
```
```
8
```
```
Returns: -1
```
This debt can't be settled, so the method returns -1.
```
{1,5,1,10,25,25,10,50,25,25}
```
```
{50,25,5,5,1,1,1,50,25}
```
```
138
```
```
Returns: 8
```
A minimum of 8 coins must change hands: John gives Mary one half-dollar, three quarters, one dime and one nickel while Mary gives John two pennies (+50+25+25+25+10+5-1-1 = 138).

{50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50}

{1,1,1,1,1,1,1,1,1,1,1,1}

Returns: 36

{5,5,5,5,5,5,5,10,10,10,10,10,10,10,10,25,25,25,25,50,50,50,50,50,50,50}

{1,1,1,1,1,1,5,5,5,10,10,10,10,10,25,25,25,25,50,50,50,50}

Returns: 18

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.