Two-Color Array Sum Parity: Algorithm and C++ Implementation

```cpp #include <iostream> #include <vector>

using namespace std;

bool canColorArray(vector<int>& arr) { int n = arr.size(); int sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; }

if (sum % 2 == 0) {
    return true;
}

for (int i = 0; i < n; i++) {
    if (arr[i] % 2 == 0) {
        return true;
    }
}

return false;

}

int main() { int t; cin >> t;

while (t--) {
    int n;
    cin >> n;
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    if (canColorArray(arr)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

return 0;

} ```

Problem Description:

Given an array of integers, determine if it's possible to color each element with one of two colors such that the sums of elements of both colors have the same parity (both even or both odd) and each color has at least one element assigned to it.

Explanation of the Algorithm:

1. Sum Calculation: Calculate the sum of all elements in the array.
2. Even Sum: If the sum is even, it's always possible to color the array with the desired properties. This is because you can assign any combination of elements to each color, and the parity of the sums will remain even.
3. Odd Sum: If the sum is odd, the only way to achieve the same parity for both colors is to have at least one even element in the array. This allows you to group one or more even elements together to balance out the odd sum.

Example:

For the array [1, 2, 4, 3, 2, 3, 5, 4], the sum is 24 (even). You can color the array in any way, and the sums of both colors will always have the same parity.

Code Breakdown:

• The canColorArray function implements the algorithm described above.
• It checks if the sum of the elements is even. If so, it returns true.
• If the sum is odd, it iterates through the array and checks if any element is even. If found, it returns true, indicating it's possible to color the array as required.
• The main function handles input/output, calling canColorArray to determine the answer for each test case.

This solution provides a simple and efficient way to solve the problem, effectively determining whether it's possible to color an array according to the given criteria.