# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Sandeep V

Tester: Jakub Safin, Satyam

Editorialist: Pratiyush Mishra

# DIFFICULTY:

1817

# PREREQUISITES:

None

# PROBLEM:

Dazzler has an interesting task for you.

You will be given an array A of N positive integers. N is always even.

Exactly N/2 elements in the array will be Even and N/2 elements will be Odd.

In one operation you should do the following steps:

- Choose two different indices i (1 \le i \le N) and j (1 \le j \le N)
- Make A[i] = A[i] + 1
- Make A[j] = A[j] - 1

After doing all the necessary number of operations (possibly none) you need to preserve the parity of each element as in the initial array A. For example if an element at the index i (1 \le i \le N) is even, at the end A[i] should be even

You need to find whether you can make all the odd elements in the array equal and all the even elements equal separately.

Print **YES** if it is possible to meet the above conditions after doing any number of operations, else print **NO**.

# EXPLANATION:

First thing to observe is that, since we can select any i and j and change A[i] = A[i] + 1 and A[j] = A[j] - 1, so we can essentially change the array to any other array A' as long as it holds the condition \sum_{i=1}^{i=n} A'[i] = sum, where sum = \sum_{i=1}^{i=n} A[i]

Now we want the final array A' to be such that N/2 of its elements are even, say 2X and rest N/2 elements to be odd, say (2Y + 1). Thus

If we subtract \frac{N}{2} from sum, we would have:

Thus for such X and Y to exist, (sum - \frac{N}{2}) would have to be divisible by N.

Thus if (sum - \frac{N}{2}) is divisible by N then it is possible, otherwise its not possible.

# TIME COMPLEXITY:

O(N), for each test case.

# SOLUTION:

Editorialistâ€™s Solution

Setterâ€™s Solution

Tester1â€™s Solution

Tester2â€™s Solution