Which ticket from 0 to n is absent?

Bits and maths Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
vals = [3, 0, 1]
n = len(vals)
acc = n
for i, v in enumerate(vals):
    acc ^= i ^ v
print(acc, n * (n + 1) // 2 - sum(vals))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 2 2

Right: both methods find that ticket 2 is absent.

Starting from n covers the one index enumerate never produces, so every present ticket cancels exactly once.

Why not the others?
  • B 2 3. The sum formula gives 6 - 4 = 2.
  • C 3 2. Starting acc at n includes the last index, which the loop does not reach.

30-second answer

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.

Practise saying it · 30 s. No recording, just a timer

Explain finding the absent ticket.

Say your answer out loud, then check which of these points you covered:

  • XOR indexes and values
  • Or the sum formula
  • O(1) memory

Deep dive

Two O(1)-memory answers (XOR and sum) are worth mentioning together.

In fixed-width languages, XOR avoids the overflow risk of the sum.

Sorting or a set also works but costs more time or memory.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
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

Common mistakes

  • Forgetting that the range includes n, so there are n + 1 possible numbers.
  • Using a set and calling it O(1) memory.

Senior take & follow-ups

Offer both formulas and say which you would choose in Python and in Kotlin.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if two tickets are absent?

    Show hint

    XOR gives a ^ b; split by a set bit as in the two-unpaired-values trick, or use sum and sum of squares.

  2. What if numbers can repeat?

    Show hint

    Then XOR fails; use a set, or cycle sort in place.

What each operation costs: Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.