3875. Construct Uniform Parity Array I

Intuition

The actual values are irrelevant, only parities are. For index i with parity p_i, the two allowed choices produce:

• nums1[i] → parity p_i
• nums1[i] - nums1[j] → parity p_i XOR p_j

So subtracting an even element leaves the parity at p_i, while subtracting an odd element flips it to 1 - p_i. In other words, index i can reach the opposite parity iff some odd element exists at a different index.

Now check each target separately, with cntOdd and cntEven the parity counts:

All even. Even elements are already fine. An odd element must flip, which needs an odd element at another index, so a lone odd is stuck, but two or more odds can pair up. Hence all-even works iff cntOdd != 1.

All odd. Odd elements are already fine. An even element must flip, which needs any odd element (necessarily at a different index, since this one is even). Hence all-odd works iff there are no evens at all, or cntOdd >= 1.

The answer is whether either target is reachable.

Approach

1. Count odds and evens in nums1.
2. allEven = (cntOdd != 1).
3. allOdd = (cntEven == 0) or (cntOdd >= 1).
4. Return allEven or allOdd.

Complexity

• Time: O(n), one counting pass
• Space: O(1)

Edge Cases

• n == 1 → no valid j exists, so only the direct choice is available; the formulas still hold (a single even gives cntOdd = 0 → all-even true; a single odd gives cntEven = 0 → all-odd true)
• Exactly one odd among evens → all-even fails, but all-odd succeeds (Example 1)
• All even → all-even trivially true (Example 2)
• All odd → all-odd trivially true
• The "different index" requirement is what makes cntOdd == 1 fail for the all-even target

from typing import List


class Solution:
    def canConstruct(self, nums1: List[int]) -> bool:
        """
        3875. Construct Uniform Parity Array I
        Time: O(n)
        Space: O(1)
        """
        odd = sum(1 for x in nums1 if x % 2)
        even = len(nums1) - odd

        # An odd element must flip parity, needing another odd at a different index.
        all_even = odd != 1
        # An even element must flip parity, needing any odd element.
        all_odd = even == 0 or odd >= 1

        return all_even or all_odd

/**
 * 3875. Construct Uniform Parity Array I
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public boolean canConstruct(int[] nums1) {
        int odd = 0;
        for (int x : nums1) {
            if (x % 2 != 0) {
                odd++;
            }
        }
        int even = nums1.length - odd;

        // An odd element must flip parity, needing another odd at a different index.
        boolean allEven = odd != 1;
        // An even element must flip parity, needing any odd element.
        boolean allOdd = even == 0 || odd >= 1;

        return allEven || allOdd;
    }
}