A raffle printed tickets numbered 0, 1, 2, ..., n, that is n + 1 tickets. One ticket got lost, and the other n were collected into a list in no particular order.
Write lost_ticket(tickets: list[int]) -> int that returns the number on the lost ticket.
lost_ticket([4, 0, 1, 3]) # 2
lost_ticket([1]) # 0
lost_ticket([0, 1, 2]) # 3 (the last ticket can be the lost one)
Constraints:
1 <= n = len(tickets) <= 2 * 10^5.- The values are distinct and each is in
[0, n].
Aim for O(n) time and O(1) extra space: no set, no boolean array, no sorted copy.
Show hint
imagine a second, complete list 0..n next to yours. Every number that is not lost then appears exactly twice across the two lists. Is there a way to combine numbers so that pairs vanish?