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
C# needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
public int StretchesTotalling(List<int> movements, int target) {
}Worked examples
| Call | Result |
|---|---|
StretchesTotalling(new List<int> { 1, 1, 1 }, 2) | 2 |
StretchesTotalling(new List<int> { 1, 2, 3 }, 3) | 2 |
StretchesTotalling(new List<int> { 1, -1, 0 }, 0) | 3 |
StretchesTotalling(new List<int> { }, 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 C#
public int StretchesTotalling(List<int> movements, int target) {
var seen = new Dictionary<int, int> { { 0, 1 } };
int running = 0, hits = 0;
foreach (var movement in movements) {
running += movement;
if (seen.ContainsKey(running - target)) hits += seen[running - target];
seen[running] = seen.ContainsKey(running) ? seen[running] + 1 : 1;
}
return hits;
}