📘

Single Number

Given an array where every element appears twice except one, find the single element. Must run in O(n) time and O(1) space.

Input:

2,2,1

Output:

Reasoning:

We initialize a variable to 0, which will hold the result of the bitwise XOR operation.
We iterate over the input array, applying the XOR operation to each element: $result = result \oplus 2$ , $result = result \oplus 2$ , $result = result \oplus 1$ .
Since $a \oplus a = 0$ and $a \oplus 0 = a$ , the XOR operation cancels out the duplicate elements, leaving only the single element: $0 \oplus 2 \oplus 2 \oplus 1 = 0 \oplus 0 \oplus 1 = 1$ .
The final output is the result of the XOR operation, which is the single element in the array.

Editor

Python 3.13.1

0/0

Run code to see test results.

📘