Syllabus Lesson 32 of 141 · Felt fast, was slow
Felt fast, was slow

Timed problem B: the double-issued ticket

Why it matters This is the matched twin of timed problem A, timed the same way. The tutor is switched off: work it out yourself.

A ticketing system hands out numbers one after another. After a failover, two machines briefly issued the same number, so in tonight's export exactly one number appears twice. The export is sorted. Support wants the repeated number to contact both customers.

The export sits on the same charged-per-read storage as the invoice archive, so each check gets a small read budget.

The data

from creative.budget import Tape
tape = Tape([300, 301, 302, 302, 303, 304])
# duplicate_ticket(tape) -> 302
Your turn

Write duplicate_ticket(tape). tape is a Tape of sorted whole numbers that run one after another from the first to the last, except that exactly one number appears twice (it may be the first or the last). Return that number. Budget: on a run of about 100,000 tickets you may read at most 100 values. len(tape) is free.

AI off: no tutor, hints or worked solution on this one. Your own thinking only.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus