Single Number

Single Number looks easy until the interviewer adds one rule. You must do it with no extra memory. That one rule is the whole point. It pushes you away from the obvious answer and toward a clever bit trick that feels like magic the first time you see it.

🎯 The Problem

You get an array of numbers. One number is alone, every other number comes in a pair. You find that lonely value, called the single number.

The rules:

• Every number appears exactly twice, except one.
• That one number appears only once.
• Find it using almost no extra memory.

Let us say the array is [4, 1, 2, 1, 2]. Here 1 shows up twice. And 2 shows up twice. But 4 shows up only once. So the answer is 4.

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

Explanation: 1 appears twice, 2 appears twice, but 4 appears only once.

You can assume exactly one number is alone. Every other number appears exactly twice.

Here is a picture of the array. Notice how each value has a twin, except one.

🐢 Approach 1: Count With a Hash Set (Brute Force)

The idea in one line: remember numbers in a set, and the leftover one is the answer.

The idea:

• A hash set remembers which numbers you have already seen.
• Walk the array once.

How it works:

• See a number the first time, add it to the set.
• See it again, remove it from the set.
• Pairs get added then removed, so they cancel out.
• At the end, only the lonely number is left.

Why it is weak:

• The set can grow as big as half the array.
• So it uses O(n) extra memory.
• The problem asked for almost no extra memory.

Here is the counting code:

from collections import Counter


def single_number(nums):
    counts = Counter(nums)
    for num, count in counts.items():
        if count == 1:
            return num

➗ Approach 2: Sort Then Scan Pairs (Better)

The idea in one line: sort the array so twins sit side by side, then find the odd one out.

The idea:

• Sorting puts equal numbers next to each other.
• Walk the sorted array two steps at a time.

How it works:

• Check each pair of neighbors at positions 0,1 then 2,3 and so on.
• If a pair does not match, the first of that pair is the single number.
• If you reach the end, the last leftover number is the answer.

Why it is weak:

• Sorting costs O(n log n) time.
• It also changes the input order unless you copy first.
• Slower than just folding the array once.

Here is the sort-then-scan code:

def single_number(nums):
    nums = sorted(nums)
    i = 0
    while i < len(nums) - 1:
        if nums[i] != nums[i + 1]:
            return nums[i]
        i += 2
    return nums[-1]

⚡ Approach 3: The XOR Trick (Best)

The idea in one line: fold the whole array with XOR and the pairs erase themselves.

The idea:

• XOR compares two numbers bit by bit.
• It gives 1 when the bits differ, 0 when they match.

How it works:

• A number XOR itself gives 0, so equal pairs cancel.
• A number XOR 0 gives back the same number, so zero does nothing.
• XOR every number into one running result.
• The pairs wipe each other clean, leaving the lonely number.

Why it is fast:

• It needs only one variable, no set and no sorting.
• That is O(1) memory and a single pass.

Here is a picture of the XOR walk over the array. Watch how pairs cancel and the lonely number survives.

Steps to Solve

1. Create one variable called result and set it to 0.
2. Walk through the array one number at a time.
3. For each number, XOR it into result.
4. The pairs cancel to zero as you go.
5. When the loop ends, result holds the single number.
6. Return result.

#include <stdio.h>

int singleNumber(int nums[], int n) {
    int result = 0;             // start at zero
    for (int i = 0; i < n; i++) {
        result ^= nums[i];      // XOR each number into result
    }
    return result;              // pairs cancelled, single number left
}

int main(void) {
    int nums[] = {4, 1, 2, 1, 2};
    int n = 5;
    printf("%d\n", singleNumber(nums, n));
    return 0;
}

4

#include <iostream>
#include <vector>
using namespace std;

int singleNumber(vector<int>& nums) {
    int result = 0;                 // start at zero
    for (int num : nums) {
        result ^= num;              // XOR each number into result
    }
    return result;                  // single number remains
}

int main() {
    vector<int> nums = {4, 1, 2, 1, 2};
    cout << singleNumber(nums) << endl;
    return 0;
}

4

public class SingleNumber {
    public static int singleNumber(int[] nums) {
        int result = 0;             // start at zero
        for (int num : nums) {
            result ^= num;          // XOR each number into result
        }
        return result;              // single number remains
    }

    public static void main(String[] args) {
        int[] nums = { 4, 1, 2, 1, 2 };
        System.out.println(singleNumber(nums));
    }
}

4

def single_number(nums):
    result = 0                 # start at zero
    for num in nums:
        result ^= num          # XOR each number into result
    return result              # single number remains


nums = [4, 1, 2, 1, 2]
print(single_number(nums))

4

function singleNumber(nums) {
  let result = 0; // start at zero
  for (const num of nums) {
    result ^= num; // XOR each number into result
  }
  return result; // single number remains
}

const nums = [4, 1, 2, 1, 2];
console.log(singleNumber(nums));

4

Let us walk through the Python version line by line and see why it works.

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

The line result = 0 sets our starting point. We pick 0 on purpose, because any number XOR 0 gives back that same number. So zero is a safe, empty start.

The line for num in nums: walks through every number in the array, one at a time. We must touch every number, because a pair only cancels when we have seen both of its members.

The line result ^= num is the heart of the trick. It means result = result ^ num. Each number gets folded into the running result. When a number appears the second time, it XORs against its own earlier copy and turns into zero. So pairs quietly wipe themselves out.

The line return result hands back what is left. After all the pairs cancel, only the lonely number remains. That is the single number we wanted.

⏱️ Time and Space Complexity

The hash set approach is fast at O(n), but it stores numbers, so it costs O(n) memory. The XOR approach also runs in O(n) time, but it keeps only one variable. So its memory is O(1). That is the whole win. We get the same speed and we drop the extra storage down to nothing. The XOR trick is the answer the interviewer is hoping to hear.

🧩 Key Takeaways

• ✅ XOR compares bits and gives 1 when bits differ, 0 when they match.
• ✅ A number XOR itself is 0, so equal pairs cancel out.
• ✅ A number XOR 0 is itself, so 0 is the perfect starting value.
• ✅ Folding the whole array with XOR leaves only the number that appears once.
• ✅ This uses O(n) time and just O(1) memory, which beats the hash set.

🚀 What’s Next?

• Number of 1 Bits
• Sum of Two Integers