Loading page…
Practice problem · medium
A ride-hailing app pays drivers in payout batches of k credits. After each trip, the driver's balance changes by the trip's earnings: a bonus is positive and a penalty is negative.
The app can settle early when two or more trips in a row net to an exact multiple of the batch size. A single trip never settles early, because its own receipt is paid separately. You check whether such a run exists.
Write has_even_run(amounts, k).
amounts[i] is the earnings of the i-th trip. It can be negative or zero.true when some run adds up to a multiple of k. A total of 0 counts as a multiple.false otherwise.Input: amounts = [5, 2, 4], k = 6
Output: trueThe trace keeps the remainder of the running total, divided by 6, and the first position where each remainder occurred. Position 0 is the empty start, with remainder 0. A remainder that comes back at least two positions later closes a run of two or more trips.
| Position | Trip | Remainder | First seen at | Distance | Result |
|---|---|---|---|---|---|
| 0 | start | 0 | store position 0 | ||
| 1 | 5 | 5 | not seen | store position 1 | |
| 2 | 2 | 1 | not seen | store position 2 | |
| 3 | 4 | 5 | position 1 | 2 | the run of trips 2 and 3 sums to 6: return true |
Input: amounts = [6], k = 6
Output: falseThe single trip is a multiple of 6, but a run needs at least two trips.
Input: amounts = [1, 2, 3], k = 7
Output: falseThe runs add up to 3, 5 and 6, and none is a multiple of 7.
0 ≤ amounts.length ≤ 100,000 (trips in the log)-10^6 ≤ amounts[i] ≤ 10^6 (earnings of one trip)1 ≤ k ≤ 10^9Trying every start and extending the run one trip at a time costs about n × n / 2 steps. For 100,000 trips that is about 5 × 10^9, far over the budget of about 10^8 a second. The huge k also means you cannot keep an array with one cell for every remainder, so you use a map.
has_even_run · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.