Practice Problems

These five problems exercise the ideas from the earlier chapters: XOR cancellation, popcount, bitmask sets and bitmask DP. Try them yourself first, then compare with the approach and Python solution.

Problem 1. The badge without a pair

A door log records an employee's badge number once on the way in and once on the way out. Exactly one person has not left yet, so their number appears only once. Given the list of numbers, find that badge in O(n) time and O(1) extra space.

Approach: since a ^ a == 0, a ^ 0 == a, and XOR ignores order, XOR-ing the whole list cancels every pair and leaves the single badge. A hash set would also work but needs O(n) memory.

from functools import reduce
from operator import xor


def still_inside(badges: list[int]) -> int:
    return reduce(xor, badges, 0)


print(still_inside([7, 3, 9, 3, 7]))   # 9

Problem 2. A table of bit counts

Given n, return a list with the number of set bits of every integer from 0 to n. Fill it in O(n) overall instead of counting each number from scratch.

Approach: i >> 1 is i with its lowest bit dropped. It is smaller than i, so its count is already known, and bits[i] = bits[i >> 1] + (i & 1). The rule bits[i] = bits[i & (i - 1)] + 1 works too.

def bit_table(n: int) -> list[int]:
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits


print(bit_table(8))   # [0, 1, 1, 2, 1, 2, 2, 3, 1]
assert bit_table(1000) == [i.bit_count() for i in range(1001)]

Problem 3. Flip one switch at a time

Start with n switches all off. Print an order that visits each of the 2^n states exactly once while changing only one switch per step. Such an order is a Gray code.

Approach: state i is i ^ (i >> 1). Going from i to i + 1 flips a run of low bits; XOR-ing that run with itself shifted right by one leaves a single bit, so neighbors differ in exactly one position. Verify by checking that each neighboring pair XORs to a value with popcount 1.

def gray_code(n: int) -> list[int]:
    return [i ^ (i >> 1) for i in range(1 << n)]


codes = gray_code(3)
print([format(c, "03b") for c in codes])
assert len(set(codes)) == 8
assert all((a ^ b).bit_count() == 1 for a, b in zip(codes, codes[1:]))

Problem 4. The cheapest team that covers every skill

A project needs k skills (k ≤ 12) and there are m candidates, each with a list of skills and a cost. Find the minimum total cost of a team whose combined skills cover all k, or -1 if impossible.

Approach: encode each skill list as a k-bit mask. Let be the cheapest way to cover the skills in mask. Adding a candidate gives . Relaxing every mask for every candidate costs . Reusing the same candidate cannot help, because OR adds nothing new while the cost grows, so in-place updates are safe.