419. Construct Uniform Parity Array I

Only parity matters. nums1[i] - nums1[j] has the same parity as nums1[i] + nums1[j], so subtracting an odd number flips a value's parity. That single degree of freedom is always enough to make every element match one common parity, so the answer is always true.

Key insight

The actual values of nums2 never matter — only whether each entry is odd or even. So track parity, written as 0 (even) or 1 (odd).

For an index i there are two moves:

• Keep: nums2[i] = nums1[i] → parity stays p_i.
• Subtract: nums2[i] = nums1[i] - nums1[j] (some j != i) → parity becomes (p_i + p_j) mod 2, because a - b and a + b always share the same parity. Subtracting an even nums1[j] keeps the parity; subtracting an odd nums1[j] flips it.

So the only way to change an element's parity is to subtract an odd element that sits at a different index.

Why it is always possible

Pick a common target parity T and check whether every index can reach it.

• If p_i == T, index i just keeps its value.
• If p_i != T, index i must flip, which needs an odd element at some j != i.

Let odd be the count of odd elements. Consider both targets:

• Target even (T = 0): the elements that must flip are exactly the odd ones. A lone odd element (odd == 1) has no other odd to borrow from, so this target works precisely when odd != 1.
• Target odd (T = 1): the elements that must flip are the even ones, and any odd element is automatically at a different index than an even one — so this target works whenever odd >= 1 (and trivially when everything is already odd).

Exactly one of these always holds: if odd == 1 the odd target works, and if odd != 1 the even target works. There is no nums1 for which both fail, so the answer is always true — matching the hint that there is only one possible answer.

Worked example

nums1 = [2, 3, 5, 8] → parities [0, 1, 1, 0], so odd = 2.

Since odd != 1, aim for all even. Keep the evens 2 and 8. For each odd, subtract another odd to flip it even: 3 - 5 = -2 (even) and 5 - 3 = 2 (even). Result nums2 = [2, -2, 2, 8] is all even → true.

Complexity

• Time: O(1) — the answer does not depend on the input at all; even counting parities is O(n) and only needed to explain the result.
• Space: O(1).

class Solution {
    public boolean uniformArray(int[] nums1) {
        // Only parity matters. An index can KEEP its value (parity unchanged) or
        // SUBTRACT another element nums1[j] (j != i), which flips its parity iff
        // nums1[j] is odd (a - b shares the parity of a + b).
        //
        // Target EVEN works unless there is exactly one odd element; target ODD
        // works whenever at least one odd element exists. One always holds, so
        // the answer is always true.
        int odd = 0;
        for (int x : nums1) {
            if ((x & 1) == 1) odd++;
        }
        return odd != 1 || odd >= 1;
    }
}