Count how many integer sequences can produce a given array of adjacent differences while staying within a fixed value range.
You are given an integer array differences of length n and two integers lower and upper.
Consider an integer sequence hidden of length n + 1 such that for every index i in [0, n - 1]:
Your task is to count how many such sequences exist if every value in hidden must lie within the inclusive range [lower, upper].
Return the number of valid sequences.
A sequence is valid if all its values are integers and each value is between lower and upper, inclusive.
Input Format
- An integer array
differences. - Two integers
lowerandupper.
The sequence values are constrained to be integers.
Output Format
- Return a single integer: the number of valid hidden sequences.
Constraints
1 <= differences.length <= $10^{5}$$-10^{5}$ <= differences[i] <= $10^{5}$$-10^{5}$ <= lower <= upper <= $10^{5}$- All sequence values must be integers and lie in
[lower, upper]. - The answer fits in a 32-bit signed integer.
Example 1
Input
differences = [3,-4,5,1,-2], lower = -4, upper = 5
Output
4
Explanation
The cumulative offsets determine a range of allowed starting values. Exactly 4 integer starting values keep every element within [-4, 5].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.