815. The Value With No Partner

A sorted list holds n integers, where n is odd. Every value appears exactly twice, with its two copies next to each other, except for one value that appears once.

Print the value that appears once.

1 1 2 3 3 4 4 8 8 -> 2 3 3 7 7 10 11 11 -> 10 1 1 2 2 3 -> 3 5 -> 5

## The obvious answer, and why a better one exists

Exclusive-or everything together. Each paired value cancels itself and the lone value survives. That is O(n), six lines, and completely correct.

The list is SORTED though, and that is information the exclusive-or trick throws away. This problem asks for O(log n), which reads only about seventeen of a hundred thousand entries.

## The pairing rule

Before the lone value, the pairs sit at index positions

(0,1) (2,3) (4,5) and so on

so every pair starts at an EVEN index, and for any even i in that region a[i] == a[i+1].

The lone value shifts everything after it by one. From then on pairs start at ODD indices, so for any even i past the lone value, a[i] != a[i+1].

That is the predicate, and it is monotone: false, false, false, then true from the lone value onwards, if you read "a[i] != a[i+1]" over even i only. The first even index where it holds is the position of the lone value.

## The invariant the loop maintains

Search only even indices. Start with lo = 0, hi = n - 1, both even since n is odd, and keep this true:

> the lone value sits at some even index in [lo, hi].

Compute mid, and if it came out odd subtract one to make it even. Then

a[mid] == a[mid+1] the pairing is still intact at mid, so the lone value is after this pair -> lo = mid + 2 a[mid] != a[mid+1] the pairing has already broken at or before mid -> hi = mid

It is lo = mid + 2 and not mid + 1, because mid + 1 is odd and odd indices are not candidates. It is hi = mid and not mid - 1 for the usual reason: mid may be the answer.

## Why the loop terminates

After the adjustment, mid is even and lo <= mid < hi. The first branch raises lo by at least two, the second lowers hi to mid, which is strictly below the old hi. So hi - lo strictly decreases and the loop ends with lo == hi, an even index holding the answer.

The adjustment matters. Without it, a mid that lands on an odd index compares the SECOND element of one pair against the FIRST of the next, which is a comparison of two unrelated values, and the search wanders.

## What is printed when the predicate never fires

If the lone value is the last element, a[mid] == a[mid+1] holds on every iteration, lo climbs to n - 1 and the answer is a[n-1]. The extreme case is n = 1: the loop never runs at all and the answer is the single element. Both are in the tests.

## Size of the numbers

The values reach 10^9 in magnitude, and they are only ever compared with each other, never summed, so nothing overflows a signed 32-bit integer. The exclusive-or solution stays in range too, but for a different reason: an exclusive-or of values that each fit cannot produce one that does not.

## Cost

Time O(log n). Space O(1) beyond the input.

Constraints - `1 ≤ n ≤ 199999`, and `n` is odd - `-1000000000 ≤ a[i] ≤ 1000000000` - Exactly one value appears once; every other value appears exactly twice.