Show problems as
Classic problem #3699HardDynamic ProgrammingPrefix Sum

Number of ZigZag Arrays I

Real-world version: Counting Sawtooth Brightness Programs
Tracked in this browser only
Read Number of ZigZag Arrays I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A light bar carries n cells in a row. A program assigns every cell an integer brightness in the closed range [l, r], so a program is an array a of length n with l <= a[i] <= r.

A program is a sawtooth when the brightness turns around at every cell it can:

  • no two neighbouring cells share a brightness, so a[i] != a[i - 1] for every i >= 1;
  • the direction alternates, so for every i with 1 <= i <= n - 2 exactly one of a[i - 1] < a[i] > a[i + 1] and a[i - 1] > a[i] < a[i + 1] holds.

Both opening directions are allowed: a program may start by going up or by going down.

Return how many sawtooth programs exist, taken modulo 10^9 + 7.

Examples

Example 1

Input
n = 3, l = 1, r = 2
Output
2

Only [1, 2, 1] and [2, 1, 2] turn around at the middle cell; the six other programs over two brightness values repeat a neighbour somewhere.

Example 2

Input
n = 3, l = 1, r = 3
Output
10

The count includes peaks such as [1, 3, 2] and troughs such as [3, 1, 2], and the reported figure is already below the modulus.

Example 3

Input
n = 4, l = 2, r = 4
Output
16

One valid program is [2, 4, 3, 4], which rises, falls, rises; the figure returned counts every such program of four cells over the brightness values 2, 3 and 4.

Example 4

Input
n = 6, l = 1, r = 2
Output
2

The two programs counted are [1, 2, 1, 2, 1, 2] and [2, 1, 2, 1, 2, 1]; each of the six cells sits in range and every step reverses the previous one.

Constraints

  • 3 <= n <= 2000
  • 1 <= l < r <= 2000

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.

Python
def sawtooth_programs(length: int, low: int, high: int) -> int:
Java
public int sawtoothPrograms(int length, int low, int high)

More on the same topics