Start learning free

LESSON 395 OF 437 · BIT MANIPULATION

Single Number in C++: O(n) Time and O(1) Space with XOR

Practice O(n) Read the full explanation

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.
Note:

Your algorithm should run in O(n) time and use O(1) extra space.


Hints:

What property can help identify a number that appears only once when all others appear twice?
Think about a bitwise operation that cancels out equal values.

XOR (^) has two key properties:
  • x ^ x = 0 — equal numbers cancel each other out
  • x ^ 0 = x — XOR with 0 leaves the number unchanged
If you XOR all elements in the array together, every duplicate pair cancels out to 0, leaving only the single number.
For example: 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4

We iterate through the array once, so the Time Complexity is O(n).
We use only one extra variable, so the Extra Space is O(1).
STEP 1 OF 4
    Ctrl + Enter to check

    C++ · BIT MANIPULATION

    Single Number in C++, explained

    Problem overview

    The function singleNumber receives a non-empty vector nums in which every value appears twice except one, and it returns that one value. For [4,1,2,1,2] the answer is 4, for [2,2,1] it is 1, and for [1] it is 1.

    The statement asks for O(n) time and O(1) extra space. That rules out sorting, which costs O(n log n), and counting with a hash map or a set, which needs O(n) extra space.

    Approach: equal numbers cancel under XOR

    The bitwise XOR operator ^ compares two numbers bit by bit and gives 1 where the bits differ. Three of its properties solve this problem:

    • x ^ x is 0: a number cancels itself.
    • x ^ 0 is x: zero changes nothing.
    • The order doesn't matter. XOR is commutative and associative, so the values can be combined in any grouping.

    Combine all the elements with XOR. The two copies of every repeated value meet somewhere in the chain and cancel to 0, wherever they sit in the vector. Only the single value remains, combined with zeros. For 4 ^ 1 ^ 2 ^ 1 ^ 2 the two 1s cancel, the two 2s cancel, and 4 is left.

    The total is kept in one int, and the vector is read once.

    Step by step

    1. Declare s as 0. Zero is the neutral value for XOR, so the first element is combined with a value that doesn't change it.
    2. Loop over nums with a range-based for and a loop variable val.
    3. Combine each value into the total: s = s ^ val.
    4. Return s after the loop.

    The solution in C++

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

    A few C++ details:

    • ^ is XOR here. In C++ the caret is not a power operator. 2 ^ 3 is 1, not 8.
    • Compound form. s ^= val does the same thing as s = s ^ val.
    • Negative values work. XOR operates on the bit patterns, and equal values have equal patterns, so they cancel for negative numbers as well. For [-5, 7, -5] the function returns 7, and for [-1, -1, -30000] it returns -30000.
    • No overflow. XOR never carries, and the result of two int operands is an int whose bits come straight from the operands, so nothing can overflow.
    • Copy or reference. The loop variable int val copies each element, which is cheap for an int. The vector is passed by reference, so the call doesn't copy it.

    Complexity

    Time: O(n). One pass over the vector, with one XOR per element.

    Space: O(1). The only extra storage is the integer s.

    Edge cases and common mistakes

    • A single element. [1] gives 0 ^ 1, which is 1.
    • Starting s at something other than 0. A non-zero start leaves that value mixed into the answer.
    • Using + or - instead of ^. Addition doesn't cancel pairs: 2 + 2 + 1 is 5, not 1.
    • Relying on the rule for other counts. The cancellation works because the repeated values appear exactly twice. A value that appears three times would leave itself behind, and the result would no longer be the single value.

    Testing

    • [2,2,1] gives 1.
    • [4,1,2,1,2] gives 4.
    • [1] gives 1.
    • [-5,7,-5] gives 7.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free