Problem solution codechef
Believe nothing you hear, and only one half that you see
On a Halloween evening, young Tim embarks on a candy-filled quest with his friends, dressed as ghouls and witches.
There are � friends, initially the �-th of them has �� candies.
To truly savor the spooky spirit, Tim wishes for everyone to have an equal number of candies.
To achieve this, he is armed with a magical operation which is as follows:
- First, Tim chooses two integers � and � (1≤�,�≤�), denoting the indices of two of his friends.
- Next, he chooses an integer � that’s at least 1, while also satisfying 2�≤��.
That is, the inequality 2≤2�≤�� should hold.
- Finally, Tim takes away 2� candies from friend � and gives them to the friend �.
That is, their candy counts change to (��−2�) and (��+2�) respectively.
Determine whether all of Tim’s friends can have an equal number of candies in the end, after some (possibly zero) operations are performed.
- The first line of input will contain a single integer �, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer � — the number of friends.
- The next line contains � space-separated integers �1,�2,…,�� — the initial number of candies each friend has.
For each test case output the answer on a new line —
"Yes" (without quotes) if it is possible to perform operations such that in the end all friends have same number of candies, and
"No" (without quotes) otherwise.
Each letter of the output may be printed in either uppercase or lowercase, i.e,
"yEs" will all be treated as equivalent.
- The sum of � over all test cases does not exceed 3⋅105
3 2 4 4 3 2 4 12 2 4 6
Yes Yes No
Test case 1: No operations are required, everyone already has an equal number of candies.
Test case 2: Consider the following sequence of operations:
- Move 22=4 candies from friend 3 to friend 1. The candy counts are now [6,4,8].
- Move 21=2 candies from friend 3 to friend 2. The candy counts are now [6,6,6].
Everyone has an equal number of candies now, as required.
Test case 3: There is no way to perform operations to have all friends with same number of candies