How many stretches add up to the figure
An investigator looks through a list of movements for every unbroken stretch that comes to a particular amount.
- Only consecutive movements count as a stretch.
- Stretches may overlap, and every one of them counts separately.
- Movements can be negative, so a longer stretch is not always a bigger total.
- Return how many stretches come to exactly the target.
stretches_totalling(movements: list<int>, target: int) → int
Where you start
def stretches_totalling(movements: list[int], target: int) -> int:
Worked examples
| Call | Result |
|---|---|
stretches_totalling([1, 1, 1], 2) | 2 |
stretches_totalling([1, 2, 3], 3) | 2 |
stretches_totalling([1, -1, 0], 0) | 3 |
stretches_totalling([], 0) | 0 |
Hint
If the running total at two points differs by the target, the stretch between them is a hit. Keep a count of every running total you have seen and look up total minus target.
Reference solution in Python
def stretches_totalling(movements: list[int], target: int) -> int:
seen = {0: 1}
running = 0
hits = 0
for movement in movements:
running += movement
hits += seen.get(running - target, 0)
seen[running] = seen.get(running, 0) + 1
return hits