Start learning free

LESSON 399 OF 441 · BIT MANIPULATION

Single Number in C#: 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 method SingleNumber receives a non-empty int[] named nums. Every value appears exactly twice, except one that appears once. The method returns that value, in O(n) time and O(1) extra space.

    For [2, 2, 1] the answer is 1. For [4, 1, 2, 1, 2] it is 4. For [1] it is 1. Values range from -30,000 to 30,000, and the array has up to 30,000 items.

    Approach: XOR cancels pairs

    The obvious solutions break the space limit. A HashSet or Dictionary of values seen so far uses O(n) memory, and sorting the array and scanning for the item without a neighbour takes O(n log n) time. The bitwise XOR operator, ^, does the job with one variable.

    XOR compares two numbers bit by bit and gives 1 where the bits differ. Three properties matter:

    • x ^ x == 0: a number cancels itself.
    • x ^ 0 == x: XOR with 0 changes nothing.
    • The order doesn't matter, so a ^ b ^ a equals a ^ a ^ b.

    XOR all the items together. Each value that appears twice cancels to 0, wherever the two copies sit in the array, and what remains is the single value XOR-ed with 0, which is the value itself. For [4, 1, 2, 1, 2] the computation is 4 ^ 1 ^ 2 ^ 1 ^ 2, which equals 4.

    Step by step

    1. Declare int s = 0;. It is the running XOR. Starting from 0 is safe because XOR with 0 leaves any value unchanged.
    2. Loop over nums with foreach (int val in nums).
    3. Fold each value in with s = s ^ val;. Equal values meet at some point and cancel, no matter how far apart they are.
    4. Return s. Everything that appeared twice has cancelled, so s is the single number.

    The solution in C#

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

    The C# details worth knowing:

    • ^ is XOR, not a power. C# has no power operator. 2 ^ 3 is 1, because 10 XOR 11 in binary is 01.
    • Negative numbers work. An int is stored in 32 bits using two's complement, and XOR works on all 32 bits. -3 ^ -3 is 0, and [-1, 5, 5] returns -1. The code doesn't need any special case for signs.
    • The same operation, shorter. s ^= val; means exactly s = s ^ val;. For int values both forms compile.
    • No overflow. The XOR of two int values is always a valid int, so unlike addition it can't overflow.

    Complexity

    Time: O(n). The loop visits each item once, and one XOR costs constant time.

    Space: O(1). The only extra memory is the variable s and the loop variable.

    Edge cases and common mistakes

    • One item. [1] gives 0 ^ 1, which is 1.
    • The single number is negative or 0. [-7, -7, -30000] returns -30000. A single 0 works too: the XOR of the pairs is 0, and 0 ^ 0 is 0.
    • Values that appear three times. XOR cancels pairs only. For [2, 2, 2, 1], the three 2s leave one 2 behind, and the method returns 3. The trick relies on the guarantee that every other value appears exactly twice.
    • Starting at nums[0]. That is fine only if the loop then skips index 0. Folding the first item in twice cancels it and returns the wrong result.
    • Using +. Adding the items doesn't cancel anything. XOR is what makes equal values disappear.

    Testing

    • [2, 2, 1] gives 1.
    • [4, 1, 2, 1, 2] gives 4.
    • [1] gives 1.
    • [-1, 5, 5] gives -1.
    • [-7, -7, -30000] gives -30000.
    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