EVEN LOVE (Editorial)

The parity (even/odd) of a sum depends entirely on the number of odd elements in the set:

Even number of odd elements $⟹$ Even total sum.

Odd number of odd elements $⟹$ Odd total sum.

To make the total sum even, we have two scenarios:

1. The initial sum is already even.

2. The initial sum is odd, but we can flip the parity of exactly one element (change an odd number to an even number, or an even number to an odd number).

The Approach

1. Check Initial Sum: Calculate the parity of the original array. If the count of odd numbers is even, the sum is already even. Output YES.

2. Search for a "Flip": If the initial sum is odd, we need to change the parity of any one a_i. We iterate through each number and check its digits:

   • If a_i is odd, we look for any even digit inside it.

   • If a_i is even, we look for any odd digit inside it.

3. Conclusion: If we find at least one such number that allows a parity flip, output YES. Otherwise, output NO.

Complexity Analysis

• Time Complexity: O(N \cdot \log(\max A_i))

• Space Complexity: $O(1)$

#include <bits/stdc++.h>
using namespace std;
#define ll long long 

void solve() {
  int n ;
  cin >> n ;
  ll sum = 0 ;
  bool ok = false ;
  for(int i = 0 ; i < n ; i ++) {
    ll x ;
    cin >> x ;
    sum += x ;
    ll val = x ;
    while(x) {
        if(val % 2 != (x % 10) % 2) ok = true ;
        x /= 10 ;
    }
  }
  cout << (((sum % 2 == 0) || (ok)) ? "YES" : "NO") << endl ;
    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("output.txt", "w", stdout);
    // freopen("input.txt", "r", stdin);
    int t;
    cin >> t ;
    
    while (t--) {
        solve();
    }
    return 0;
}