Problems › TypeScript › patterns
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.
stretchesTotalling(movements: list<int>, target: int) → int
Where you start
function stretchesTotalling(movements: number[], target: number): number {
}Worked examples
| Call | Result |
|---|---|
stretchesTotalling([1,1,1], 2) | 2 |
stretchesTotalling([1,2,3], 3) | 2 |
stretchesTotalling([1,-1,0], 0) | 3 |
stretchesTotalling([], 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 TypeScript
function stretchesTotalling(movements: number[], target: number): number {
const seen = new Map<number, number>([[0, 1]]);
let running = 0;
let hits = 0;
for (const movement of movements) {
running += movement;
hits += seen.get(running - target) ?? 0;
seen.set(running, (seen.get(running) ?? 0) + 1);
}
return hits;
}