Academy
mediumJS ES5#108

Encontrar al impar (odd count)

Prompt

Given an array of signed 32-bit integers (−2³¹ … 2³¹−1), find the one that appears an odd number of times. There will always be exactly one such number.

The range is part of the contract: the intended O(1)-space answer relies on JavaScript's bitwise operators, which coerce to signed 32-bit. Say so in your answer.

Solution

function findOdd(arr) {
  return arr.reduce((acc, n) => acc ^ n, 0)
}
Mentor's take

This is the XOR trick, the classic "find the single one" bit-manipulation pattern. It works because XOR has three properties: n ^ n === 0 (a value cancels itself), n ^ 0 === n (zero is the identity), and it's commutative/associative (order doesn't matter). XOR-ing the whole array makes every even-count value cancel out in pairs, leaving only the odd-count survivor. O(n) time, O(1) space — a single reduce with no allocations.

The honest alternatives are worth naming, because they're what most candidates reach for:

  • Frequency map then find the odd count: O(n) time but O(n) space, two passes. Correct, and more general — it works when there are multiple odd-count values.
  • Nested count per element (filter(...).length inside a loop): O(n²). The usual trap.

So XOR is the only O(1)-space answer, but it leans hard on the problem's guarantee of exactly one odd-count number. If two values appeared an odd number of times, XOR would return their combined bits — garbage. Stating that precondition is what separates "memorized the trick" from "understands it". It also works fine with negative numbers, since XOR operates on two's-complement bit patterns.

The second precondition is the one candidates miss: JavaScript's bitwise operators coerce both operands to signed 32-bit integers. ^ on anything outside ±2³¹ silently truncates, so findOdd returns a wrong number rather than throwing — and it can't handle non-integers at all. In a language with real 64-bit ints the trick is unconditional; in JS it carries a range contract. Name that contract, or fall back to the frequency map, which has none.

Red flag: using the XOR trick without saying why it works or when it breaks — an interviewer will immediately ask "what if there are two odd ones?" Also the O(n²) count-inside-loop if you skip the trick entirely.

Say it: "XOR cancels pairs — n^n is 0 and 0 is the identity — so folding the array leaves the odd-count element in O(n) time and O(1) space. Two preconditions: exactly one odd-count value, and the values fit in signed 32 bits, because that's what JS bitwise operators coerce to."