Loading page…
Practice problem · medium
Kestrel Bank charges small fees on an account, such as a transfer fee or a card fee. Each ledger entry records one fee in integer units. A fee is never negative, and some entries carry no fee at all.
A new fee-relief policy reviews every stretch of consecutive fee entries whose total stays within an allowance. Before the policy goes live, the policy team wants to know how much review work it creates. For each ledger, they ask how many such stretches it has.
Write count_within(fees, allowance).
fees[i] is the fee on ledger entry i, in integer units, never negative. It may be 0.i to entry j with i ≤ j.fees[i] + ... + fees[j] ≤ allowance.(i, j) counts once.0. The ledger is never empty.Input: fees = [3, 1, 0, 4, 2], allowance = 5
Output: 10| right | Joins | Total after joining | Leaves | Total after | left | Stretches ending at right | count |
|---|---|---|---|---|---|---|---|
| 0 | 3 | 3 | none | 3 | 0 | 1 | 1 |
| 1 | 1 | 4 | none | 4 | 0 | 2 | 3 |
| 2 | 0 | 4 | none | 4 | 0 | 3 | 6 |
| 3 | 4 | 8 | 3 | 5 | 1 | 3 | 9 |
| 4 | 2 | 7 | 1, 0, 4 | 2 | 4 | 1 | 10 |
At right = 4, the fee 0 leaves but the total stays at 6, so the 4 must leave too.
Input: fees = [0, 0, 5, 0], allowance = 0
Output: 4With an allowance of 0, only stretches of zero fees fit: three in the first run of zeros and one in the last.
Input: fees = [7, 9], allowance = 5
Output: 0Every single fee is over the allowance, so no stretch fits.
1 ≤ fees.length ≤ 10^50 ≤ fees[i] ≤ 10^60 ≤ allowance ≤ 10^14Checking every pair of start and end is O(n^2): about 5 × 10^9 steps at n = 10^5. Aim for O(n).
Read the answer's size too. When every stretch fits, the count is n(n + 1) / 2 = 5,000,050,000, beyond a 32-bit integer. Fees can total 10^11 units. Use 64-bit integers for the count and the total in Java and C++.
count_within · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.