easy

Single Number

Find the one number in an array that does not appear exactly twice.

1. Define the problem

Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. XOR every value together with a running XOR . A value XORed with itself cancels to 0, so every pair vanishes and only the lone value survives.

Constraints

  • 1 ≤ nums.length ≤ 3 × 104
  • -3 × 104 ≤ numsi ≤ 3 × 104
  • Each element appears twice except for one element which appears once

Example

Inputnums = [4, 1, 2, 1, 2]
Output4

Explanation 1 and 2 each appear twice and cancel out under XOR, leaving 4.

2. Know the words first

In plain terms

XOR
The ^ operator: a bit comes out 1 only when its two input bits differ. XOR-ing a value with itself always gives 0, and XOR-ing anything with 0 leaves it unchanged — that's why pairs cancel out.
3. Visualize the solution

XOR every value into one running result

XOR every value into one running result
Statusresult = 0

result starts at 0. XOR in nums[0] = 4.

What happens in this step

0 ^ 4
  0 = 00000000
  4 = 00000100
      --------
      00000100  =  4

XOR-ing with 0 never changes anything — result becomes 4.
Step 1 of 5

Steps to visualize

  1. Start a running result at 0.
  2. XOR the running result with each value in nums, in order.
  3. A value that has already appeared once cancels itself out, leaving 0 for that pair.
  4. After the last value, whatever remains is the single number.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

XOR every value into one running result
Statusresult = 0

result starts at 0. XOR in nums[0] = 4.

What happens in this step

0 ^ 4
  0 = 00000000
  4 = 00000100
      --------
      00000100  =  4

XOR-ing with 0 never changes anything — result becomes 4.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function singleNumber(nums) {
  let result = 0;

  for (const num of nums) {
    result ^= num;
  }

  return result;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [4, 1, 2, 1, 2]4example from the docstring
nums = [7]7smallest valid input, one element and no pairs
nums = [-1, -1, -2]-2negative values still cancel correctly under XOR
nums = [2, 1, 1]2the unique value appears first in the array
nums = [0, 1, 0]1zero itself appears as a paired value
nums = [5, 3, 9, 3, 5, 9, 8]8several pairs before the single value

Keep reading