Unique Lone Integer: find the number that appears only once

You're in a Google phone screen and the interviewer says: "I have an array of integers where every number appears twice except one. Find the odd one out, and do it in constant space." If your first instinct is to reach for a hash map, that's a reasonable start. But this problem has a trick that makes the hash map unnecessary, and interviewers at Google, Apple, Adobe, and Amazon use it specifically to test whether you know that trick. The trick is XOR.

TL;DR

XOR every element in the array together, starting from 0. Pairs of identical numbers cancel out (a ^ a = 0), and XORing with 0 leaves a number unchanged (a ^ 0 = a). After one pass through the array, the accumulator holds the unique element. This runs in O(n) time and O(1) space. No sorting, no hash maps, no extra memory.

The Problem

Given a non-empty array of integers nums where every element appears exactly twice except for one unique element, find that single number. The constraint that matters: solve it in O(1) space.

singleNumber([2, 2, 1])       => 1
singleNumber([4, 1, 2, 1, 2]) => 4
singleNumber([1])              => 1

Constraints:

• 1 ≤ nums.length ≤ 1,000,000
• -1,000,000 ≤ nums[i] ≤ 1,000,000
• Every element appears twice except one

Edge Cases

1. Single element: The array contains only one number, which is the answer.
2. Negative numbers: XOR works on two's complement representation, so negatives are handled automatically.
3. Zero in the array: [0, 1, 0] returns 1. XOR with 0 is the identity operation.
4. Large arrays: The algorithm is a single pass with no extra allocation, so it handles arrays of a million elements without issue.

Why XOR?

Before jumping to the solution, it helps to understand why XOR is the right tool here. XOR (exclusive or) is a bitwise operation with two properties that make it perfect for this problem:

1. Self-cancellation: a ^ a = 0. Any number XORed with itself produces zero.
2. Identity: a ^ 0 = a. Any number XORed with zero stays the same.

Two additional properties ensure the order of elements does not matter:

3. Commutativity: a ^ b = b ^ a. You can swap operands freely.
4. Associativity: (a ^ b) ^ c = a ^ (b ^ c). You can regroup operations freely.

Put these together and you get the core idea: if you XOR all elements in the array, every number that appears twice cancels to zero, and the lone integer remains.

For the array [4, 1, 2, 1, 2], you can mentally regroup the XOR chain:

4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4

Tracing Through the Algorithm

For [2, 2, 1], the accumulator evolves step by step:

The pair of 2s cancel, leaving 1. For a longer example, [4, 1, 2, 1, 2]:

Even though the pairs are not adjacent, the XOR accumulation still produces the correct result. The intermediate values (5, 7, 6) look unpredictable, but every paired element eventually cancels its contribution.

What XOR Looks Like at the Bit Level

To build deeper intuition, here is the same [2, 2, 1] example in binary:

At each position, XOR compares the bits: same bits produce 0, different bits produce 1. When the same number appears twice, every bit matches on the second XOR, driving the result back to zero for those bits.

Alternative Approaches

Before writing the XOR solution, it is worth considering two alternatives and why XOR wins:

Hash map approach: Walk through the array, storing counts in a map. Then scan the map for the key with count 1. This is O(n) time but O(n) space, since the map can hold up to n/2 entries.

Sorting approach: Sort the array, then scan adjacent pairs. The unpaired element is the answer. This is O(n log n) time with O(1) space (if sorting in place), but it modifies the input or requires O(n) space for a copy.

XOR approach: O(n) time and O(1) space, with no modification to the input array. It is strictly better on both dimensions.

Implementation

Here is the solution in Java. The structure is the same in every language: initialize a result variable to 0, XOR every element, return the result.

Prefer a different language? Jump to solutions in other languages.

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

Three lines of logic. The result variable acts as the accumulator. Each ^= folds the next element into the running XOR. When the loop finishes, every paired value has cancelled and only the lone integer remains.

Edge Case: Single Element

When the array has exactly one element, the loop body executes once:

0 ^ element = element. The identity property handles this case with no special branching.

Complexity Analysis

Time Complexity: O(n)

The algorithm iterates through the array once. Each iteration performs a single XOR operation, which is O(1) on any modern CPU (it maps directly to a hardware instruction). Total work: n iterations times O(1) per iteration = O(n).

Space Complexity: O(1)

One integer variable (result) is the only allocation beyond the input. No auxiliary data structures, no recursion stack. This holds regardless of whether the array has 3 elements or 1 million.

This is optimal for the problem. You must read every element at least once (any unread element could be the unique one), so O(n) time is a lower bound. You cannot do better than O(1) auxiliary space.

Common Pitfalls

1. Using a hash map by default: Many candidates reach for a HashMap or dictionary immediately. That works, but the interviewer is often looking for the XOR trick specifically. Start with the hash map approach if you need a working solution fast, then optimize.

2. Forgetting the initial value: The accumulator must start at 0, not at nums[0]. Starting at nums[0] means you skip the first element in the XOR chain. Some implementations start at nums[0] and iterate from index 1 - that also works, but result = 0 with a full loop is cleaner.

3. Worrying about overflow: XOR does not change the magnitude of numbers the way addition does. There is no integer overflow risk with XOR, because the result is always within the range of the input values' bit widths.

4. Assuming elements are positive: The XOR approach works identically for negative numbers. Two's complement representation means -1 ^ -1 = 0 just like 1 ^ 1 = 0.

Interview Tips

When solving this in an interview:

1. Start by confirming constraints: "Every element appears exactly twice except one?" This rules out problems where elements can appear three or more times (which requires a different approach).

2. Show the brute-force first: Mention the hash map solution to demonstrate that you can solve the problem. Then say, "But we can do better on space using XOR."

3. Explain the XOR properties: State the two key properties (self-cancellation and identity). Walk through a small example like [2, 2, 1] on the whiteboard.

4. Handle follow-ups:

   • "What if two elements appear once?" (Single Number III: XOR all, then split by a differing bit)
   • "What if every element appears three times except one?" (Single Number II: count bits modulo 3)
   • "Can you do it without XOR?" (Math approach: 2 * sum(set) - sum(all))

5. Test with edge cases: Single element, negative numbers, zero in the array.

Key Takeaways

• XOR's self-cancellation (a ^ a = 0) and identity (a ^ 0 = a) properties let you find a unique element in one pass with no extra memory.
• The algorithm is O(n) time and O(1) space, which is provably optimal since every element must be examined at least once.
• Commutativity and associativity of XOR mean the element positions do not matter. Pairs cancel regardless of where they appear.
• The hash map approach works but uses O(n) space. Sorting works but runs in O(n log n). XOR is the only method that is optimal on both axes.
• This is the entry point to a family of bit manipulation problems. Mastering Single Number makes Single Number II and III much more approachable.

Solutions in Other Languages

The algorithm is identical in every language: initialize an accumulator to 0, XOR each element, return the result.

Python

class Solution:
    def single_number(self, nums: list[int]) -> int:
        result = 0
        for num in nums:
            result ^= num
        return result

Python's ^ operator works on arbitrary-precision integers, so there is no overflow concern even with very large values.

JavaScript

class Solution {
  singleNumber(nums) {
    let result = 0;
    for (let num of nums) {
      result ^= num;
    }
    return result;
  }
}

TypeScript

class Solution {
  singleNumber(nums: number[]): number {
    let result = 0;
    for (const num of nums) {
      result ^= num;
    }
    return result;
  }
}

C++

#include <vector>

class Solution {
public:
  int singleNumber(std::vector<int> &nums) {
    int result = 0;
    for (int num : nums) {
      result ^= num;
    }
    return result;
  }
};

Go

func SingleNumber(nums []int) int {
    result := 0
    for _, num := range nums {
        result ^= num
    }
    return result
}

Scala

Scala's reduce with the XOR operator makes this a one-liner:

class Solution {
  def singleNumber(nums: Array[Int]): Int = {
    nums.reduce(_ ^ _)
  }
}

Kotlin

Kotlin uses the xor infix function instead of the ^ operator:

class Solution {
  fun singleNumber(nums: IntArray): Int {
    var result = 0
    for (num in nums) {
      result = result xor num
    }
    return result
  }
}

Swift

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var result = 0
        for num in nums {
            result ^= num
        }
        return result
    }
}

Rust

impl Solution {
    pub fn single_number(&self, nums: Vec<i32>) -> i32 {
        let mut result = 0;
        for &num in nums.iter() {
            result ^= num;
        }
        result
    }
}

Rust's ownership model means nums is consumed here. In practice, you might take a slice &[i32] instead.

Ruby

class Solution
  def single_number(nums)
    result = 0
    nums.each do |num|
      result ^= num
    end
    result
  end
end

C#

public class Solution {
    public int SingleNumber(int[] nums) {
        int result = 0;
        foreach (int num in nums) {
            result ^= num;
        }
        return result;
    }
}

Dart

class Solution {
  int singleNumber(List<int> nums) {
    int result = 0;
    for (int num in nums) {
      result ^= num;
    }
    return result;
  }
}

PHP

class Solution {
    public function singleNumber(array $nums): int {
        $result = 0;
        foreach ($nums as $num) {
            $result ^= $num;
        }
        return $result;
    }
}

Practice

Unique Lone Integer is a great warm-up for bit manipulation problems. Once you are comfortable with it, try these related challenges:

• Single Number II (every element appears three times except one) - requires counting bits modulo 3
• Single Number III (two elements appear once) - uses XOR plus bit partitioning
• Counting Bits - another problem where understanding binary representation pays off
• Power of Two - a one-line bit trick once you see the pattern

Consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you are just starting out or preparing for your next role, building fluency with bit manipulation will give you an edge that most candidates lack.

Happy XORing!