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;
}