# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

**Setter:** abhi_inav

**Testers:** iceknight1093, tabr

**Editorialist:** hrishik85

# DIFFICULTY:

1013

# PREREQUISITES:

None

# PROBLEM:

We are given an array B. Elements of B are formed from the elements of array A using the following operation

- B_{i} = (A_i + A_{i+1}) % 2 for 1 <= i <= N-1
- B_N = (A_1 + A_N) % 2
- B_i = 0 OR B_i = 1

Given the array B, can there exist an array A such that B can be formed from A?

# EXPLANATION:

When do we get 0â€™s in B? We will get 0s if both Ai and Ai+1 are even or both are odd. When 2 numbers are even or both numbers are odd, their sum is necessarily even.

When do we get 1â€™s in B? We will get 1s if either A_i is even and A_{i+1} is odd or vice versa.

Implementation

Lets try and construct the array A from array B given the conditions above. Let the 1st element in array A be [1]

We can iterate across B from i = 1 to i = N - 1.

For each i in B from i = 1 to i = N - 1, if B_i = 0, then we append A_{i+1} = A_i

For each i in B from i = 1 to i = N - 1, if Bi not equal to 0, then we append A_{i+1} = (A_i + 1) basically if A_i is odd, we are appending an even number. If A_i is even, we are appending an odd number

Now, our array A is constructed with N elements and we need to check if the 1st and Nth element of A meet the condition which will create BN. We can do this by checking for the condition

If (A_1 + A_N) % 2 = B_N, then A is a valid array. Correspondingly, B then is also a valid array.

If (A_1 + A_N) % 2 is not equal to B_N, then A is invalid. Hence B cannot be constructed from A

# TIME COMPLEXITY:

Time complexity is O(N).

# SOLUTION:

## Editorialist's Solution

```
t=int(input())
for _ in range(t):
n=int(input())
brr=list(map(int,input().split()))
arr=[]
i=0
arr.append(1)
while i<n-1:
if brr[i]==0:
arr.append(arr[i])
else:
arr.append(arr[i]+1)
i=i+1
#print(arr)
if (arr[0]+arr[n-1])%2==brr[n-1]:
print('YES')
else:
print('NO')
```