Reaching zero by
split and merge

Two operations, one target: [0]

Two moves are allowed, repeatable in any order. Split: replace B with any C, D where C + D = B. Merge: replace P, Q with P XOR Q. Goal: reduce the array to a single [0]. The tempting move is to simulate — which to merge, what to split into, in what order. There are far too many sequences. The right question is different: what property survives every operation?

The sum survives split; its parity survives both

A split leaves the total sum untouched: C + D = B. A merge does change the sum — 9+17=26 becomes 9 XOR 17 = 24 — so the sum itself isn't invariant. But watch the last bit. There's an identity:

P + Q = (P XOR Q) + 2·(P AND Q)

The gap P + Q − (P XOR Q) = 2·(P AND Q) is always even, so P + Q and P XOR Q always share parity. Split can't change the sum; merge can't change its parity. Therefore sum mod 2 is invariant.

Split, merge, watch parity refuse to move

Tap a token to select it. Split the selected one into two parts (enter the first part); Merge two selected tokens into their XOR. Odd values carry a red underline, even ones teal. The parity box up top never changes color no matter what you do — that's the invariant, live. Reach a single [0] when the sum is even.

Try 1 (odd → the parity box stays red, zero is unreachable) or 2 5 7 (even → Auto-solve collapses it to [0]).

The recipe: shatter into ones, then pair

The invariant proves odd is hopeless. Sufficiency needs a construction, and it's simple. Split every value all the way down to 1s — a number v becomes v ones. The array turns into S ones total, where S is the sum.

So every even-sum array reaches zero, and no odd-sum array can. That closes both directions: possible if and only if the sum is even.

Reading the answer off the parity

The sum is even exactly when the count of odd elements is even — the two tests are equivalent, since only odd terms flip the last bit.

One bit is all that matters

// Clearest: sum in long (avoids int overflow), check the low bit
boolean canMakeZero(int[] arr) {
    long sum = 0;
    for (int v : arr) sum += v;
    return sum % 2 == 0;
}

// Deeper: track only parity — no overflow possible at all
boolean canMakeZero(int[] arr) {
    int parity = 0;
    for (int v : arr) parity ^= (v & 1);
    return parity == 0;
}

O(N) time, O(1) space — optimal, since you must at least read every element to know its parity.

Five ways it slips

Arbitrary operations + "is it reachable?" → find an invariant

This breaks cleanly from the binary-search problems: there's no search space to halve. When a problem allows many arbitrary transformations and asks only whether a target is reachable, the move is to ask what every operation preserves — parity, a sum, a GCD, a count, something mod m. If an operation only ever changes a quantity by multiples of m, that quantity mod m is invariant.

The wording is the tell: "sorted + O(log n)" says binary search; "arbitrary allowed operations + feasibility" says invariant. And a complete answer pairs the impossibility proof with a construction to earn the if-and-only-if.

Reconstruct it, don't memorize it

1. Feasibility under arbitrary operations → stop simulating, look for an invariant.
2. Split keeps the sum (C+D=B); merge changes it but keeps its parity (P+Q and P XOR Q agree mod 2).
3. So sum mod 2 never changes; [0] is even, so an odd sum is impossible.
4. Even sum is enough: split everything into 1s, pair them (1 XOR 1 = 0), merge the zeros.
5. Answer: even sum → Yes, odd sum → No. Track just the low bit; O(N), O(1).