Number of ZigZag Arrays II
Real-world version: Counting Alternating Runs of a Given LengthThe statement here is our own: the same inputs, outputs and technique.
A reading log is a list of n whole numbers, each between l and r inclusive.
The log alternates when every step from one reading to the next changes direction: it goes up, then down, then up, and so on, or down, then up, then down, and so on. No two neighbouring readings may be equal.
Return how many alternating logs there are, modulo 10^9 + 7.
Examples
Example 1
- Input
- n = 3, l = 1, r = 3
- Output
- 10
Of the twenty-seven logs of three readings over 1, 2 and 3, ten alternate: five that go up then down and five that go down then up.
Example 2
- Input
- n = 3, l = 1, r = 2
- Output
- 2
Only 1, 2, 1 and 2, 1, 2 alternate.
Example 3
- Input
- n = 7, l = 4, r = 9
- Output
- 16544
Six readings are allowed and the log holds seven of them, and the count comes out of carrying the two families forward six steps.
Constraints
- 3 <= n <= 10^9
- 1 <= l < r <= 75
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def zig_zag_arrays(n: int, l: int, r: int) -> int:public int zigZagArrays(int n, int l, int r)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's