EqualizeBags | Topcoder Archive

Problem Statement

There are N bags of candy. The bags are numbered from 0 to N-1, inclusive. For each i, bag number i contains bags[i] pieces of candy.

You want to give the bags of candy to N kids. In order to do that, you need to make sure that each bag contains the same number of candies.

Before you give the bags to the kids, you want to eat some candies from the bags. More precisely, you would like to eat exactly E pieces of candy.

You are given the int N, the int[] bags and the int E. Determine whether it's possible to eat exactly E candies in such a way that after you are done eating, each bag contains the same number of candies. Return "possible" if it can be done and "impossible" if it cannot be done.

Definition

Class:: EqualizeBags
Method:: check
Parameters:: int, int[], int
Returns:: String
Method signature:: String check(int N, int[] bags, int E)
(be sure your method is public)

Notes

The return value is case-sensitive and must be all lowercase.

Constraints

N will be between 1 and 50, inclusive.
bags will have N elements.
Each element of bags will be positive.
The sum of all elements of bags will not exceed 10^9.
E will be between 0 and 10^9, inclusive.

Examples

```
3
```
```
{5, 47, 5}
```
```
42
```
```
Returns: "possible"
```
If you eat all 42 candies from the middle bag (bag #1), you will be left with three bags containing 5 candies each.
```
3
```
```
{5, 47, 5}
```
```
43
```
```
Returns: "impossible"
```
Regardless of how you eat 43 candies, the three bags won't be equal once you're done.
```
3
```
```
{5, 47, 6}
```
```
43
```
```
Returns: "possible"
```
In this scenario you should eat 42 candies from bag #1 and one candy from bag #2.
```
1
```
```
{47}
```
```
42
```
```
Returns: "possible"
```
If there's just one bag the condition "each bag contains the same number of candies" is always satisfied.
```
1
```
```
{42}
```
```
47
```
```
Returns: "impossible"
```
There is no way to eat 47 candies in this scenario.

{1001, 1005, 1002, 1004, 1003}

Returns: "possible"

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.