Equal Parity Sum

★★★★★

4.2

4 votes

, Greedy algorithm, Implementation, Linear Search, Algorithms

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A[1\dots N]$ containing $N$ integers. You can apply the following operation atmost once :

Choose a subarray $A[i \dots j]$ with $\;1 \le i \le j\le N$ and multiply $-1$ to all elements of the subarray.

Find if it possible to make the sum of integers on the odd indices of $A$ equal to the sum of integers on the even indices.

Input format

The first line contains $T$ denoting the number of test cases. The description of $T$ test cases is as follows:
For each test case:
- The first line contains a single integer $N$ denoting the size of array $A$ .
- The second line contains $N$ integers $A_1, A_2, \dots, A_N$ - denoting the elements of $A$ .

Output format

For each test case, print YES if it is possible to achieve to requied goal, otherwise print NO in a separate line.

Constraints

$1 \leq T \leq 10^5 \\ 2 \leq N \leq 5\cdot10^5\\ \\-10^9 \le A_i \le 10^9 \\ \text{Sum of $N$ over all test cases does not exceed} \;5\cdot 10^5.$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

In the first test case, apply the operation on the subarray $A[3\dots 4]$ making $A = [1, 5, 2, -3, -1]$ , Now the sum of elements on the odd indices is $1 + 2 -1 = 2$ , and the sum of elements on the even indices is $5 - 3 = 2$ .

In the second test case, it is impossible to achieve the goal.