Bits and maths cheat sheet

The one value without a partner

XOR all the values. XOR is associative and commutative, x ^ x = 0 and x ^ 0 = x, so every pair cancels and only the unpaired value remains. O(n) time, O(1) memory.

def unpaired(vals: list[int]) -> int:
    acc = 0
    for v in vals:
        acc ^= v  # equal pairs cancel to 0
    return acc

Count the 1 bits in a number

x & (x - 1) clears the lowest 1 bit, because subtracting 1 flips that bit and every 0 below it. Repeat until x is 0, counting the steps. The loop runs once per 1 bit, at most O(log x) times, with O(1) space. In real code, x.bit_count() does this directly.

def ones(x: int) -> int:
    count = 0
    while x:
        x &= x - 1  # clears the lowest 1 bit
        count += 1
    return count

1-bit counts for every number from 0 to n

Dropping the last bit of i (i >> 1) gives a smaller number whose count is already known; add back the dropped bit (i & 1). So bits[i] = bits[i >> 1] + (i & 1). One pass, O(n) time and O(n) space for the table, which beats recounting each number on its own in O(n log n).

def ones_table(n: int) -> list[int]:
    bits = [0] * (n + 1)  # bits[0] stays 0
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)  # drop last bit, add it back
    return bits

Which ticket from 0 to n is absent?

XOR every index 0 to n with every value: each present number appears twice and cancels, leaving the absent one. The sum formula n(n + 1) / 2 minus the sum of values also works and cannot overflow in Python. Both are O(n) time and O(1) memory.

def absent_ticket(tickets: list[int]) -> int:
    acc = len(tickets)  # index n is never produced below
    for i, t in enumerate(tickets):
        acc ^= i ^ t  # present numbers cancel
    return acc

Bit tricks worth knowing

A handful cover most questions: x & 1 tests odd; x >> k and x << k divide or multiply by 2ᵏ; x & (x - 1) clears the lowest 1 bit; x & -x keeps only the lowest 1 bit; x | (1 << k) sets bit k, x & ~(1 << k) clears it and x ^ (1 << k) flips it; a mask of n bits represents a subset of n items.

Working modulo 10⁹ + 7

Counts like the ways to arrange or climb can grow past any fixed integer size. Reporting them modulo a large prime keeps numbers small. Addition, subtraction and multiplication can be reduced at every step: (a + b) % m and (a × b) % m. Division needs a modular inverse: pow(b, m - 2, m) when m is prime. Python never overflows, but reducing still keeps the numbers small and fast.