Odd Even Binary String solution codechef – Chef had an array $A$ of length $N$ such that 1≤��≤�1≤Ai​≤N for all $1\le i\le N$.

Odd Even Binary String solution codechef

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?

Odd Even Binary String solution codechef

• 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).

Odd Even Binary String solution codechef

Sample 1:

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

YES
NO
YES

Odd Even Binary String solution codechef

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$.