Count Analogous Arrays
Problem statement
A secret integer array of length $n$ is hidden, but you know two things about it: every element of the secret array lies in $[\text{lowerBound}, \text{upperBound}]$, and you are given its array of consecutive differences consecutiveDifference, where consecutiveDifference[i] $= s[i] - s[i+1]$ (note the order: earlier minus later).
An array $a$ is analogous to the secret array if it has the same length, every element is in $[\text{lowerBound}, \text{upperBound}]$, and it has the exact same consecutive differences: $a[i] - a[i+1] = s[i] - s[i+1]$ for all $i$.
Count how many analogous arrays exist. Return 0 if none.
countAnalogousArrays(consecutiveDifference: List[int], lowerBound: int, upperBound: int) -> int
Constraints
- Bounds and differences are integers.
Example
consecutiveDifference = [-2, -1, -2, 5]
lowerBound = 3, upperBound = 10
Fixing $a_0$ determines the whole array. The valid starts give $[3,5,6,8,3]$, $[4,6,7,9,4]$, $[5,7,8,10,5]$. Answer: 3.
Show hint
How many values do you actually need to choose before the entire array is determined?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.
Related free problems
- Consecutive Numbers SumMedium