Start learning free

LESSON 396 OF 438 · BIT MANIPULATION

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

    PYTHON · BIT MANIPULATION

    Single Number in Python, explained

    Problem overview

    The method singleNumber receives a non-empty list of integers, nums. Every value appears exactly twice except one, which appears once. The method returns that single value.

    For nums = [4, 1, 2, 1, 2] the 1 and the 2 each appear twice, and the 4 appears once, so the answer is 4. For [2, 2, 1] the answer is 1, and for [1] it is 1, because the list may hold just the single value.

    The statement asks for O(n) time and O(1) extra space. That rules out sorting, which costs O(n log n), and a set or dictionary of the values seen so far, which needs O(n) memory.

    Approach: let equal numbers cancel

    The obvious ways to find the odd one out are to count each value with a dictionary, or to sort the list and look for a value whose neighbours differ. Both work, and both pay in time or in memory. The idea here avoids both by using the bitwise XOR operator, ^.

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

    • x ^ x = 0: a number XORed with itself cancels completely.
    • x ^ 0 = x: XOR with 0 changes nothing.
    • The order doesn't matter, because XOR is commutative and associative.

    So if you XOR all the values together, you can rearrange them mentally so that each pair sits side by side. Every pair becomes 0, the zeros disappear, and only the single value is left. For example, 4 ^ 1 ^ 2 ^ 1 ^ 2 equals 4 ^ (1 ^ 1) ^ (2 ^ 2), which is 4 ^ 0 ^ 0, which is 4.

    A smaller example shows it at the bit level. 5 is 101 in binary and 3 is 011. Then 5 ^ 3 is 110, which is 6. XORing 5 again gives 110 ^ 101 = 011, which is 3: the second 5 undoes the first one.

    Nothing needs to be remembered about which values were seen. One running number is enough, and that is the O(1) space.

    Step by step

    1. Start an accumulator s at 0. Zero is the identity for XOR, so the first value passes through unchanged.
    2. Loop over nums with the loop variable val, so each element is visited once.
    3. Fold each value into s with s = s ^ val. After the loop, every value that appeared twice has been XORed in twice and has cancelled.
    4. Return s. What is left is the value that was XORed in only once.

    The solution in Python

    class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        s = 0
        for val in nums:
            s = s ^ val
        return s

    The Python details worth knowing:

    • The operator is ^, not **. In Python, ^ is bitwise XOR. Exponentiation is **. Writing 2 ^ 3 gives 1, not 8.
    • Augmented form. s ^= val does the same as s = s ^ val. The longer form shows the operation more clearly while you learn it.
    • Negative numbers work. Python integers have no fixed width and behave as if negative numbers had infinitely many leading 1 bits. XOR still cancels equal values, so -3 ^ 5 ^ -3 is 5. The constraints allow values from -30000 to 30000, and the method handles all of them.
    • No overflow. Python integers grow as needed, so there is nothing to wrap around. The result also always has a value that was in the list, so it fits in the same range.
    • Ordinary iteration. for val in nums walks the list from the first element to the last without any index. The list isn't changed.

    Complexity

    Time: O(n). The loop visits each of the n elements once and does a constant amount of work for each: one XOR on small integers.

    Space: O(1). The only extra storage is the integer s and the loop variable val. It doesn't depend on the length of the list.

    Edge cases and common mistakes

    • A single element. [1] gives 0 ^ 1, which is 1.
    • The single value is 0. [0, 5, 5] returns 0. That is correct, and the answer being 0 doesn't mean that nothing was found.
    • Negative values. [-3, 5, -3] returns 5.
    • Starting the accumulator at 1 or at nums[0] with a loop over everything. Starting at 1 pollutes the result with an extra XOR of 1. Starting at nums[0] and then looping over the whole list XORs the first value in twice, which cancels it. Start at 0, or start at nums[0] and loop over the rest.
    • Using addition or subtraction. Adding the values doesn't cancel pairs. XOR does, because each bit is its own opposite.
    • Relying on the input rule. The method assumes every other value appears exactly twice. If a value appeared three times, it wouldn't cancel. For example, [2, 2, 2, 1] returns 3, not 1, which is the XOR of the 2 left over with the 1. This lesson's tests only use lists that follow the rule.

    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 PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free