Tag Archives: Odd Even Binary String solution codechef

Odd Even Binary String solution codechef

Odd Even Binary String solution codechef – Chef had an array  of length  such that 1≤��≤� for all 1≤�≤�.

Odd Even Binary String solution codechef

Chef constructed another binary array  of length  in the following manner:

  • ��=1 if the frequency of element  in  is odd.
  • ��=0 if the frequency of element  in  is even.

Such an array  is called the parity encoding array of .

For example, if �=[1,1,2,3], then �=[0,1,1,0].

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

Odd Even Binary String solution codechef

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

Output Format

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

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

Odd Even Binary String solution codechef

  • 1≤�≤105
  • 1≤�≤105
  • ��∈{0,1}
  • Sum of  over all test cases does not exceed 2⋅105.

Sample 1:

Input

Output

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: �=[2,4,3,3] is a valid array for the given array .

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

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