Solution: Single Number

Let’s solve the Single Number problem using the Bitwise Manipulation pattern.

We'll cover the following

Statement

Given an array of integers, where every element appears twice except for one, find the element that occurs only once.

Note: The solution must have linear runtime and constant space complexity.

Constraints:

  • 1≤1 \leq nums.length ≤103\leq 10^3
  • −3Ă—103≤-3 \times 10^3 \leq nums[i] ≤3Ă—103\leq 3 \times 10^3

Solution

We can use the bitwise XOR operator to find the single number in the array efficiently. XOR has the following two properties:

  • Performing the XOR of a number with itself returns zero.
  • Performing the XOR of zero with a number returns the same number.

Using the above XOR properties, we can perform the XOR of all the numbers in the input array. The duplicate numbers will cancel each other out, and the single number will be left.

We take the recurring bitwise XOR of the element with the result from the previous iteration until the end of the array.

The algorithm is as follows:

  1. Initialize a result variable with 0.

  2. Iterate over each element of the array, take the bitwise XOR of the element with the result variable, and store the resultant value in the result variable.

  3. After completing the traversal, the result variable will have the element that appeared once.

  4. Return the result variable.

The slides below illustrate how we would like the algorithm to run.