Count Zigzag Arrays with Large Length
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Count arrays of length `n` whose integer entries satisfy all of the following:
- Every entry is in the inclusive range `[l,r]`.
- No neighboring entries are equal.
- No three consecutive entries form a strictly increasing or strictly decreasing sequence.
Return the count modulo `1000000007`.
```cpp
class Solution {
public:
int zigZagArrays(int n, int l, int r);
};
```
### Examples
**Example 1:**
```text
Input: n = 1000000000, l = 7, r = 8
Output: 2
Explanation: After choosing the first entry, the two available values force each subsequent entry. The arrays beginning with 7 and with 8 are the only valid ones, regardless of this large length.
```
**Example 2:**
```text
Input: n = 5, l = 1, r = 3
Output: 26
Explanation: There are twenty-six valid arrays. For example, [1,3,2,3,1] and [3,1,2,1,3] satisfy all three conditions. Arrays with an equal neighboring pair or a strictly monotone triple are excluded.
```
### Constraints
- `3 <= n <= 1000000000`.
- `1 <= l < r <= 75`.
### Clarifying Questions
- Are `l` and `r` both included? Yes.
- May entries two positions apart be equal? Yes; only neighboring equality is prohibited.
- Are arrays starting with either an increase or a decrease allowed? Yes, provided every condition holds.
- Is the actual array required as output? No; return only the modular count.
### What a Strong Answer Covers
- Every permitted value and both kinds of forbidden consecutive triple.
- Counting each valid array exactly once, with correct modular arithmetic.
- The smallest value range and the full, large length bound.
- A completeness proof and time and memory bounds appropriate for all inputs.
### Follow-up Questions
- How does requesting the exact count instead of its residue affect numeric representation?
- Would a repeated entry necessarily be invalid if another entry lies between its two occurrences?
```hint Use a repeated counting transformation
Unequal neighbors make the comparison directions alternate. Record counts by the final value and comparison direction. The same linear transition applies at every additional position, so repeated squaring can apply it for a very large number of positions.
```
Overview: Count zigzag arrays for lengths up to one billion and a bounded value range. Includes fresh examples, modular counting, a complete proof, and C++ code.