Loading page…
Practice problem · medium
A payments app keeps a ledger of settled entries. Each entry is the net change it made to a merchant's balance, so a refund is a negative number.
Finance wants to know how many streaks of consecutive entries add up to exactly one amount, for example the amount of a disputed payout. The ledger can hold 100,000 entries.
Write count_streaks(amounts, target).
amounts[i] is the net change of the i-th ledger entry. It can be negative or zero.target. Two streaks that cover different entries count separately, even when they have the same values.int, so use a 64-bit result.Input: amounts = [2, -1, 3, -2, 1, 4], target = 3
Output: 3The trace keeps the running total, and a table of how often each running total has occurred. The table starts with total 0 once, before any entry.
| Step | Entry | Running total | Looks up (total − 3) | Streaks found | Table after |
|---|---|---|---|---|---|
| 0 | start | 0 | 0 | 0: 1 | |
| 1 | 2 | 2 | −1, not in the table | 0 | 0: 1, 2: 1 |
| 2 | −1 | 1 | −2, not in the table | 0 | adds 1: 1 |
| 3 | 3 | 4 | 1, found once | 1 | adds 4: 1 |
| 4 | −2 | 2 | −1, not in the table | 0 | 2: 2 |
| 5 | 1 | 3 | 0, found once | 1 | adds 3: 1 |
| 6 | 4 | 7 | 4, found once | 1 | adds 7: 1 |
The three streaks are [3], [2, -1, 3, -2, 1] and [-2, 1, 4]. The output is 3.
Input: amounts = [5], target = 5
Output: 1The single entry is a streak, and it starts at the very first entry.
Input: amounts = [0, 0, 0], target = 0
Output: 6Every streak adds up to 0: three streaks of one entry, two of two entries and one of three entries.
0 ≤ amounts.length ≤ 100,000 (entries in the ledger)-10^6 ≤ amounts[i] ≤ 10^6 (net change of one entry)-10^9 ≤ target ≤ 10^9Trying every start and extending the streak one entry at a time costs about n × n / 2 steps. For 100,000 entries that is about 5 × 10^9, far over the budget of about 10^8 a second. Running totals can reach 10^11, and the answer can reach about 5 × 10^9, so both need 64 bits.
count_streaks · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.