Blog

Find Single Number In An Array

I came across the following array questions on LeetCode and was amazed by one of the solutions achieving a linear runtime complexity and without using extra memory. Declaration: I didn’t come up with the solution.

Problem Statement

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • Each element in the array appears twice except for one element which appears only once.

Solution: Bit Manipulation

Concept

  • If we take XOR of zero and some bit, it will return that bit
    • a ⊕ 0 = a
  • If we take XOR of two same bits, it will return 0
    • 0 ⊕ a = 0
  • a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b

So we can XOR all bits together to find the unique number. Here is the solution for Java: 

class Solution {
  public int singleNumber(int[] nums) {
    int a = 0;
    for (int i : nums) {
      a ^= i;
    }
    return a;
  }
}

Complexity Analysis

  • Time complexity : O(n). We only iterate through nums, so the time complexity is the number of elements in nums.
  • Space complexity : O(1).
Tags: