Array Coloring: Determine Two-Color Possibility with Parity

Array Coloring: Determine Two-Color Possibility with Parity

This problem asks you to determine if you can color all elements of an array in two colors (let's say red and blue) such that the sum of all red elements and the sum of all blue elements have the same parity (both even or both odd), and each color has at least one element.

Example:

If the array is [1, 2, 4, 3, 2, 3, 5, 4], we can color it as follows: [1, 2, 4, 3, 2, 3, 5, 4], where the sum of the blue elements is 6 and the sum of the red elements is 18.

Input:

• The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases.
• Each test case begins with a line containing an integer n (2 ≤ n ≤ 50) — the length of the array a.
• The next line contains n integers a1, a2, …, an (1 ≤ ai ≤ 50) — the elements of the array a.

Output:

For each test case, output 'YES' (without quotes) if it is possible to color the array in two colors in such a way that the sums of the elements of both colors have the same parity and each color has at least one element colored, and 'NO' otherwise.

C++ Code:

#include <iostream>
#include <vector>

using namespace std;

bool canColorArray(vector<int>& array) {
    int n = array.size();
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += array[i];
    }
    if (sum % 2 != 0) {
        return false;
    }
    int oddCount = 0, evenCount = 0;
    for (int i = 0; i < n; i++) {
        if (array[i] % 2 == 0) {
            evenCount++;
        } else {
            oddCount++;
        }
    }
    if (oddCount != 0 && evenCount != 0) {
        return true;
    }
    return false;
}

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

Explanation:

1. canColorArray Function:

   • Calculates the sum of all elements in the array.
   • If the sum is odd, it's impossible to have equal parity sums for two colors, so it returns false.
   • Counts the number of odd and even elements.
   • If both counts are non-zero, it's possible to create two groups with equal parity sums, so it returns true.
   • If either count is zero, it's impossible to create two groups with equal parity sums, so it returns false.

2. main Function:

   • Reads the number of test cases t.
   • For each test case, reads the length of the array n and the elements of the array.
   • Calls the canColorArray function to determine if the array can be colored as required.
   • Prints 'YES' if possible, 'NO' otherwise.

Key Concepts:

• Parity: The property of a number being even or odd.
• Sum of Even/Odd Numbers: The sum of two even numbers is even, the sum of two odd numbers is even, and the sum of an even and an odd number is odd.