Practice: Finding the Missing Ticket Number With XOR

Tickets 0 to 7 were sold and one is missing from the box: find it with XOR, then decide whether the number sold is a power of two.

Finding a missing number with XOR reuses the cancellation that finds an unpaired value. A raffle sold tickets numbered 0 to 7, and the box holds 3 7 0 1 6 2 4: one is missing. Find it with XOR in O(1) extra space and say why it works, then decide with one bit trick whether 8, the number of tickets sold, is a power of two.

Show the answer and a solution

Ticket 5 is missing. XOR every number from 0 to 7 with every ticket found: each ticket in the box appears twice, once expected and once found, and cancels, so only the missing number is left. The XOR of 0 to 7 is 0, so the tickets start from 0.

The running XOR over the expected numbers, then the tickets

Inputexpected 0 to 7, tickets 3 7 0 1 6 2 4

0 to 7, running 0
1. 0
2. 0
3. 0
4. 0
5. 0
6. 0
7. 0
8. 0
The XOR of 0 to 7 is 0
Ticket 3, running 3
1. 0
2. 0
3. 0
4. 0
5. 0
6. 0
7. 1
8. 1
Ticket 3
Ticket 7, running 4
1. 0
2. 0
3. 0
4. 0
5. 0
6. 1
7. 0
8. 0
Ticket 7 turns the bits worth 2 and 1 off and the bit worth 4 on
Ticket 0, running 4
1. 0
2. 0
3. 0
4. 0
5. 0
6. 1
7. 0
8. 0
Ticket 0 changes nothing
Ticket 1, running 5
1. 0
2. 0
3. 0
4. 0
5. 0
6. 1
7. 0
8. 1
Ticket 1
Ticket 6, running 3
1. 0
2. 0
3. 0
4. 0
5. 0
6. 0
7. 1
8. 1
Ticket 6
Ticket 2, running 1
1. 0
2. 0
3. 0
4. 0
5. 0
6. 0
7. 0
8. 1
Ticket 2
Ticket 4, running 5
1. 0
2. 0
3. 0
4. 0
5. 0
6. 1
7. 0
8. 1
Ticket 4 leaves 5, the missing ticket

Result5 is left: the only number expected and not found.

8 is a power of two, because 8 > 0 and 8 & 7 is 0; the test has to exclude 0, which also gives 0. The listing runs both.

missing_ticket.pypy

def missing_number(tickets: list[int], sold: int) -> int:
    running = 0
    for number in range(sold):
        running ^= number
    for ticket in tickets:
        running ^= ticket
    return running


def is_power_of_two(x: int) -> bool:
    return x > 0 and (x & (x - 1)) == 0


tickets = [3, 7, 0, 1, 6, 2, 4]
print("missing ticket:", missing_number(tickets, 8))
print("8 sold is a power of two:", is_power_of_two(8))
print("7 sold is a power of two:", is_power_of_two(7))
print("0 sold is a power of two:", is_power_of_two(0))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

missing ticket: 5
8 sold is a power of two: True
7 sold is a power of two: False
0 sold is a power of two: False

The search is O(n) time and O(1) extra space for n tickets. Summing 0 to 7 and subtracting the tickets also works; XOR does it without any running value needing more bits than the largest ticket number.

Algorithms

← → move through sections and cards