# PROBLEM LINK:

**Setter:** Akash Bhalotia

**Tester:** Rahul Dugar

**Editorialist:** Ishmeet Singh Saggu

# DIFFICULTY:

Simple

# PREREQUISITES:

Maths

# PROBLEM:

There are N integers in an array A. Two players take turns alternatively in placing signs (+ or -) before them, and then they all are added. The sign can be placed before any element of the array that has not been assigned a sign yet. All elements must be assigned a sign. Player 1 wins if the resulting sum is even, else player 2 wins. Find out who shall win if they both play optimally.

# EXPLANATION:

If the sum of elements of the array A is even then player 1 will win otherwise player 2 will win. It doesnâ€™t matter how signs are placed by the players. Why? letâ€™s see.

Consider the sum of all elements, sum = X. Now suppose in some game the i-th element A_i of the array has (-) sign placed before it, so the new sum, sum' = sum - 2*A_i and as we are subtracting (2*A_i) which is an even quantity, the parity of sum' will be equal to sum. So the parity will not change regardless of you put the (-) sign or (+) sign in front of the element and will be equal to the sum of all elements.

# TIME COMPLEXITY:

- Time complexity per test case is O(N).

# SOLUTIONS:

## Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
long long sum = 0, in;
cin >> n;
for(int i = 0; i < n; i ++) {
cin >> in;
sum += in;
}
if(sum % 2) cout << 2 << "\n";
else cout << 1 << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t --) {
solve();
}
return 0;
}
```