Loading page…
Practice problem · medium
A ride-hailing app numbers the trips of a shift from 1 to n. At the end of the shift the app writes all n trip ids into a log.
A bug in the log writer saved one trip id twice and lost another id. You must report both: the id that is saved twice, and the id that is missing.
Write missing_and_repeated(ids).
ids has n entries, and every entry is between 1 and n.[repeated, missing].Input: ids = [1, 2, 2, 4]
Output: [2, 3]The trace keeps a set of the ids seen. After the pass it looks for the number from 1 to n that is not in the set.
| i | id | In the set? | Set after |
|---|---|---|---|
| 0 | 1 | no | 1 |
| 1 | 2 | no | 1, 2 |
| 2 | 2 | yes: repeated = 2 | 1, 2 |
| 3 | 4 | no | 1, 2, 4 |
Now n = 4, and the numbers 1 to 4 are checked against the set. The number 3 is not there, so the missing id is 3. The output is [2, 3].
Input: ids = [1, 1]
Output: [1, 2]For n = 2, the id 1 appears twice and 2 is missing.
Input: ids = [3, 2, 3, 1]
Output: [3, 4]For n = 4, the id 3 appears twice and 4 is missing.
2 ≤ ids.length ≤ 100,000 (trips in a shift)1 ≤ ids[i] ≤ ids.length (trip ids)Counting each number from 1 to n by scanning the list costs n × n steps, about 10^10 at n = 100,000. A set, or a count table, finds both numbers in two passes of n steps. Because every id is between 1 and n, a plain array of n + 1 flags works even better than a hash set.
missing_and_repeated · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.