Start learning free

LESSON 403 OF 445 · BIT MANIPULATION

Single Number in Rust: 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

    RUST · BIT MANIPULATION

    Single Number in Rust, explained

    Problem overview

    The function single_number takes a non-empty vector of integers, nums. Every value appears exactly twice except one, which appears once. The function returns that single value.

    For nums = [4, 1, 2, 1, 2] the answer is 4: the 1s and the 2s come in pairs, and 4 has no partner. For [1] the answer is 1, and for [2, 2, 1] it is 1.

    The task asks for O(n) time and O(1) extra space. A hash map of counts or a sorted copy would work, but the map uses O(n) space and sorting costs O(n log n). Neither fits the budget.

    Approach: XOR cancels equal values

    The bitwise XOR operator, written ^ in Rust, compares two numbers bit by bit and gives a 1 wherever the bits differ. Three of its properties solve this problem:

    • x ^ x = 0: a value XORed with itself cancels out.
    • x ^ 0 = x: XOR with zero changes nothing.
    • XOR is commutative and associative, so the order of the operands doesn't matter.

    Because of the last property, XORing the whole vector gives the same result as regrouping the values so that equal ones sit next to each other. Each pair becomes 0, the zeros vanish, and only the single value is left. For the example: 4 ^ 1 ^ 2 ^ 1 ^ 2 equals 4 ^ (1 ^ 1) ^ (2 ^ 2), which is 4 ^ 0 ^ 0, which is 4.

    The same works with bits. XORing 6 (00000110) and 3 (00000011) gives 00000101, which is 5. XORing 5 with 3 again gives back 6, so a value that appears twice leaves no trace.

    Step by step

    1. Declare an accumulator. s is a mutable i32 that starts at 0, the value that changes nothing under XOR.
    2. Loop over the vector with for val in nums, one value at a time.
    3. Fold each value into the accumulator with s = s ^ val. After the loop, every pair has cancelled itself.
    4. Return s.

    The solution in Rust

    impl Solution {
    fn single_number(nums: Vec<i32>) -> i32 {
        let mut s: i32 = 0;
        for val in nums {
            s = s ^ val;
        }
        return s;
    }
}

    A few Rust details:

    • for val in nums consumes the vector. The loop moves nums into the iterator, and val is an owned i32, not a reference. That is fine here because the function doesn't use nums afterwards. Looping over &nums would give &i32 values, and s ^ val still works on them, because Rust implements ^ for references to integers too.
    • Negative numbers. Negative values are stored in two's complement, and XOR works on all 32 bits, so the trick doesn't care about signs. [-3, 5, -3] returns 5.
    • No overflow. XOR only combines bits and never carries, so the result always fits in i32, unlike a running sum.
    • s = s ^ val can be written s ^= val. Both do the same thing.
    • return s; is valid at the end of a function. Leaving off both return and the semicolon, with just s, is the more usual Rust style.

    Complexity

    Time: O(n). The loop visits each element once and XOR on an i32 is a single operation.

    Space: O(1). The only extra storage is the variable s. The vector is the input, and the loop doesn't copy it.

    Edge cases and common mistakes

    • A single element. [1] gives 0 ^ 1, which is 1.
    • Starting the accumulator at a non-zero value. The accumulator must start at 0. Any other start value would stay in the result.
    • Using + or - instead of ^. Adding the values gives their total, which says nothing about which one is single.
    • Using & or |. These don't cancel equal values. Only XOR has x ^ x = 0.
    • Relying on the pairing rule. The method needs every other value to appear exactly twice. In [7, 7, 7] the result is 7 whether or not that is meaningful, because three copies leave one behind. With other counts the result would not identify a single value.

    Testing

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