Loading page…
Practice problem · medium
A ride-hailing app offers a promotion for two trips booked together. The promotion applies when the fares of the two trips add up to a promo total.
You get the fares of a batch of trips and the promo total. You count how many pairs of trips qualify. Every pair of positions is counted, so the same fares at different positions count as different pairs.
Write count_pairs_total(orders, total).
orders[i] is the fare of the i-th trip.i < j with orders[i] + orders[j] == total.int, so use a 64-bit result.Input: orders = [1, 5, 3, 3, 3], total = 6
Output: 4The trace keeps a table of how many times each fare has been seen. For each fare it adds the number of earlier fares that make the total.
| i | fare | Partner (6 - fare) | Earlier partners | Pairs so far |
|---|---|---|---|---|
| 0 | 1 | 5 | 0 | 0 |
| 1 | 5 | 1 | 1 | 1 |
| 2 | 3 | 3 | 0 | 1 |
| 3 | 3 | 3 | 1 | 2 |
| 4 | 3 | 3 | 2 | 4 |
The pairs are (0, 1), (2, 3), (2, 4) and (3, 4), so the output is 4.
Input: orders = [2, 2, 2, 2], total = 4
Output: 6Every pair of the four fares adds up to 4, and there are 6 pairs of positions.
Input: orders = [1, 2], total = 10
Output: 0The two fares add up to 3, not 10, so there are no pairs.
0 ≤ orders.length ≤ 100,000 (trips in a batch)0 ≤ orders[i] ≤ 500,000,000 (fares in minor units)0 ≤ total ≤ 1,000,000,000Checking every pair costs about n × n / 2, about 5 × 10^9 at n = 100,000. A table of counts finds the number of earlier partners in one step. The answer itself can reach about 5 × 10^9 (every pair), which does not fit in a 32-bit int, so the result type is long.
count_pairs_total · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.