Implement Bit Manipulation TricksStep 3 of 5

Find the Single Number

12345

Step 3: Find the Single Number

XOR has two magic properties: x ^ x == 0 and x ^ 0 == x. It is also commutative, so order does not matter.

Given a list where every element appears exactly twice except one, XOR-ing all elements cancels every pair and leaves the unique value. This runs in one pass with no extra memory.

Implement single_number(nums) to return the element that appears only once.

Hints
Starter code
def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count


def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0


def single_number(nums):
    """Return the element that appears exactly once.

    Every other element appears twice. XOR-ing all values cancels the pairs.
    """
    # TODO: fold every value into an accumulator with XOR, starting at 0.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step