Odd Even Binary String Codechef Solution

Problem

Chef had an array $A$ of length $N$ such that 1≤��≤�1≤Ai​≤N for all $1\le i\le N$. Chef constructed another binary array $B$ of length $N$ in the following manner:

• ��=1Bi​=1 if the frequency of element $i$ in $A$ is odd.
• ��=0Bi​=0 if the frequency of element $i$ in $A$ is even.

Such an array $B$ is called the parity encoding array of $A$.

For example, if $A=[1,1,2,3]$, then $B=[0,1,1,0]$.

Unfortunately, Chef completely forgot the array $A$ and vaguely remembers the parity encoding array $B$. He is now wondering whether there exists any valid array $A$ for which the parity encoding array is $B$. Can you help Chef?

Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ — the size of the arrays $A$ and $B$.
• The second line of each test case contains $N$ space-separated integers �1,�2,…,��B1​,B2​,…,BN​ denoting the parity encoding array $B$.

Output Format

For each test case, output YES if there exists any valid array $A$ for which the parity encoding array is $B$. Otherwise, output NO.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

Constraints

Sample 1:

3
4
0 1 0 1
5
1 1 1 1 0
6
1 1 1 1 1 1

YES
NO
YES

Explanation:

Test case $1$: $A=[2,4,3,3]$ is a valid array for the given array $B$.

Test case $2$: It can be proven that there does not exist any array $A$ for the given parity encoding array $B$.

Test case $3$: $A=[1,2,3,4,5,6]$ is a valid array for the given array $B$.