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

Timed problem A: the missing invoice

Why it matters This one is timed from when you first open it to when you first pass. The AI tutor is allowed. Use it however you normally would.

An auditor checks that invoice numbers have no gaps. Invoices are numbered one after another, and the archive stores them sorted. In this batch exactly one number between the first and the last stored invoice is missing, and the auditor wants to know which.

The archive is a cold-storage service that charges per value read, and audits run on thousands of batches, so each audit gets a small read budget.

The data

from creative.budget import Tape
tape = Tape([1000, 1001, 1002, 1004, 1005])
# missing_invoice(tape) -> 1003
Your turn

Write missing_invoice(tape). tape is a Tape of sorted, distinct whole numbers that would be consecutive except that exactly one number strictly between the first and the last is missing (so the tape holds at least two numbers). Return the missing number. Budget: on a run of 100,000 invoices you may read at most 100 values. len(tape) is free.

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