Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    EasyBit Manipulation

    Single Number

    Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

    You must implement a solution with a linear runtime complexity and use only constant extra space.

    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 * 10^4
    • -3 * 10^4 <= nums[i] <= 3 * 10^4
    • Each element in the array appears twice except for one element which appears only once.
    View original on LeetCode ↗

    The space constraint rules out a hash set of seen values (that would be O(n) space). The trick is a property of XOR: x ^ x = 0 and x ^ 0 = x, and XOR is commutative and associative. So if every value except one appears exactly twice, XOR-ing the whole array together cancels every paired value down to zero, leaving only the value that appeared once.

    Hash Set

    Time O(n)Space O(n)

    Walk the array, adding each new value to a set and removing it if it is already there. Whatever remains in the set at the end is the answer.

    class Solution:
        def singleNumber(self, nums: list[int]) -> int:
            seen = set()
            for num in nums:
                if num in seen:
                    seen.remove(num)
                else:
                    seen.add(num)
            return seen.pop()

    This works, but it uses O(n) space for the set, which violates the “constant extra space” requirement even though it is linear time.

    XOR Accumulator

    OptimalTime O(n)Space O(1)

    XOR every number in the array into a running accumulator, starting at 0. Each value that appears twice XORs with itself and vanishes (x ^ x = 0); the leftover value XORs with 0 and survives (x ^ 0 = x). Since XOR does not care about order, it does not matter where the duplicates and the single value fall in the array.

    class Solution:
        def singleNumber(self, nums: list[int]) -> int:
            result = 0
            for num in nums:
                result ^= num
            return result

    Tracing nums = [4, 1, 2, 1, 2], watch the bit strip: every value sets its bits on the first pass, and a duplicate toggles those same bits back off, cancelling the pair.

    Input

    41212

    Incoming value

    0
    8
    0
    4
    0
    2
    0
    1

    Accumulator (start)

    0
    8
    0
    4
    0
    2
    0
    1

    0decimal

    1 / 6
    currentseenresult

    The accumulator, an XOR running total, starts at 0000 (0). Each value of the array is folded in one at a time; watch the bit strip update every step.

    Correctness: XOR is commutative and associative, so the order of operations does not matter — the final accumulator equals the XOR of all distinct values that appear an odd number of times, which here is exactly the single number.

    Complexity: one pass over the array with O(1) work per element → O(n) time. Only a single integer accumulator is kept → O(1) space, satisfying the constraint the hash set approach could not.

    More Bit Manipulation practice