[soilution] Take it Easy solution codechef – little bits and big deals

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 $N$ friends, initially the $i$ -th of them has $A_{i}$ 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 $i$ and $j$ ( $1 \leq i, j \leq N$ ), denoting the indices of two of his friends.
Next, he chooses an integer $k$ that’s at least $1$ , while also satisfying $2^{k} \leq A_{i}$ .
That is, the inequality $2 \leq 2^{k} \leq A_{i}$ should hold.
Finally, Tim takes away $2^{k}$ candies from friend $i$ and gives them to the friend $j$ .
That is, their candy counts change to $(A_{i} - 2^{k})$ and $(A_{j} + 2^{k})$ 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.

Input Format

The first line of input will contain a single integer $T$ , 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 $N$ — the number of friends.
- The next line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ — the initial number of candies each friend has.

Output Format

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", "YES", and "yEs" will all be treated as equivalent.

Constraints

$1 \leq T \leq 1 0^{3}$
$1 \leq N \leq 1 0^{5}$
$1 \leq A_{i} \leq 1 0^{3}$
The sum of $N$ over all test cases does not exceed $3 \cdot 1 0^{5}$

Sample 1:

Input

Output

Yes
Yes
No

Explanation:

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 $2^{2} = 4$ candies from friend $3$ to friend $1$ . The candy counts are now $[6, 4, 8]$ .
Move $2^{1} = 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