Loading page…
Practice problem · medium
A shop's card terminal sends a check-in to the payment service from time to time. The service stores each check-in as the number of seconds since the terminal was installed. No two check-ins share a second, and they are stored in increasing order.
A monitoring rule looks for terminals that run on a fixed timer. It counts triples of check-ins where the gap between the first and the second equals the gap between the second and the third. You are asked to write that count.
Write count_even_triples(times).
times[i] is the time of the i-th check-in, in seconds. The list is strictly increasing: every time is larger than the one before.i < j < k. It is evenly spaced when times[j] - times[i] == times[k] - times[j].Input: times = [1, 3, 4, 5, 7, 9]
Output: 6Fix each check-in j as the middle one. Put lo right before it and hi right after it, and compare the left gap times[j] - times[lo] with the right gap times[hi] - times[j].
| j | lo | hi | Times (lo, j, hi) | Left gap | Right gap | Action | count after |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 2 | 1, 3, 4 | 2 | 1 | right is smaller: hi becomes 3 | 0 |
| 1 | 0 | 3 | 1, 3, 5 | 2 | 2 | equal: count, lo and hi move, lo leaves the list | 1 |
| 2 | 1 | 3 | 3, 4, 5 | 1 | 1 | equal: count, lo becomes 0, hi becomes 4 | 2 |
| 2 | 0 | 4 | 1, 4, 7 | 3 | 3 | equal: count, lo leaves the list | 3 |
| 3 | 2 | 4 | 4, 5, 7 | 1 | 2 | left is smaller: lo becomes 1 | 3 |
| 3 | 1 | 4 | 3, 5, 7 | 2 | 2 | equal: count, lo becomes 0, hi becomes 5 | 4 |
| 3 | 0 | 5 | 1, 5, 9 | 4 | 4 | equal: count, lo leaves the list | 5 |
| 4 | 3 | 5 | 5, 7, 9 | 2 | 2 | equal: count, hi leaves the list | 6 |
The check-in at index 5 (time 9) has nothing after it, so it is never a middle. The six triples are (1, 3, 5), (3, 4, 5), (1, 4, 7), (3, 5, 7), (1, 5, 9) and (5, 7, 9).
Input: times = [0, 10, 20, 30]
Output: 2The timer fires every 10 seconds. The triples are (0, 10, 20) and (10, 20, 30). Times 0, 10 and 30 do not work, because the gaps are 10 and 20.
Input: times = [1, 2, 4, 8, 16]
Output: 0Every gap is twice the one before it, so no check-in sits halfway between two others.
1 ≤ times.length ≤ 5,000 (check-ins)0 ≤ times[i] ≤ 1,000,000,000 (seconds since the install)times is strictly increasingChecking every triple costs about n × n × n ÷ 6 triples. At n = 5,000 that is about 2 × 10^10, roughly 200 seconds at 10^8 operations a second. Checking every pair costs about n × n ÷ 2 pairs, about 12.5 million, which is fast.
The count is at most about n × n ÷ 4, so about 6.25 million. It fits in a 32-bit integer, and so does every gap, because the times stay at or below 10^9.
count_even_triples · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.