Welcome to Subscribe On Youtube

3699. Number of ZigZag Arrays I

Description

You are given three integers n, l, and r.

A ZigZag array of length n is defined as follows:

  • Each element lies in the range [l, r].
  • No two adjacent elements are equal.
  • No three consecutive elements form a strictly increasing or strictly decreasing sequence.

Return the total number of valid ZigZag arrays.

Since the answer may be large, return it modulo 109 + 7.

A sequence is said to be strictly increasing if each element is strictly greater than its previous one (if exists).

A sequence is said to be strictly decreasing if each element is strictly smaller than its previous one (if exists).

 

Example 1:

Input: n = 3, l = 4, r = 5

Output: 2

Explanation:

There are only 2 valid ZigZag arrays of length n = 3 using values in the range [4, 5]:

  • [4, 5, 4]
  • [5, 4, 5]​​​​​​​

Example 2:

Input: n = 3, l = 1, r = 3

Output: 10

Explanation:

There are 10 valid ZigZag arrays of length n = 3 using values in the range [1, 3]:

  • [1, 2, 1], [1, 3, 1], [1, 3, 2]
  • [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2]
  • [3, 1, 2], [3, 1, 3], [3, 2, 3]

All arrays meet the ZigZag conditions.

 

Constraints:

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

Solutions

Solution 1

  • int zigZagArrays(int n, int low, int high) {
    int range = high - low;
    int mod = 1000000007, *dp, *ptr, *end, i = 1, goingUp = 1;
    long long ans = 0;
    if (range < 1 || !(dp = malloc(range * sizeof(int)))) return 0;
    ptr = dp;
    end = dp + range;
    while (ptr < end) *ptr++ = 1;
    ptr = dp + 1;
    while (ptr < end) *ptr += ptr[-1], ptr++;
    for (; i < n - 1; i++) {
        if (goingUp) {
            ptr = dp + range - 2;
            while (ptr >= dp) *ptr += ptr[1], *ptr -= *ptr >= mod ? mod : 0, ptr--;
        } else {
            ptr = dp + 1;
            while (ptr < end) *ptr += ptr[-1], *ptr -= *ptr >= mod ? mod : 0, ptr++;
        }
        goingUp ^= 1;
    }
    ptr = dp;
    while (ptr < end) ans += *ptr++;
    free(dp);
    return (int) (ans * 2 % mod);
}

All Problems

All Solutions