Horje
Count of non-decreasing Arrays

Given two arrays A[] and B[] both of size N, the task is to count the number of non-decreasing arrays C[] of size N such that for (1 ≤  i ≤ N)   A[i] ≤ C[i] ≤ B[i] holds true. 

Array is non-decreasing if C[i] ≤ C[i + 1] holds for every i (1-based indexing) such that (1 ≤ i ≤ N – 1).

Examples:

Input: A[] = {1, 1}, B[] = {2, 3}
Output: 5
Explanation: {1, 1}, {1, 2}, {1, 3}, {2, 2} and  {2, 3}  are the possible arrays that follow above conditions

Input: A[] = {2, 2, 2}, B[] = {2, 2, 2}
Output: 1
Explanation: {2, 2, 2} is the only array possible that follows the above conditions.

Naive approach: The Brute Force to solve the problem is as follows:

Naive Dynamic Programming can be written for this problem

  • dp[i][j] represents the maximum number of arrays formed of size i and j being the last element chosen.
  • Recurrence relation: dp[i][j] = summation of dp[i – 1][k] for k from 1 to Cmax ( Cmax is the maximum value possible in array C[] )

Time Complexity: O(N3)
Auxiliary Space: O(N2)

Efficient Approach:  The above approach can be optimized based on the following idea:

The above DP can be optimized with Prefix sum performing on DP values.

  • dp[i][j] = summation of dp[i – 1][k] where k is from 1 to Cmax
  • This calculation can be avoided as this is calculating for each j from 1 to j which takes O(N2).
  • Prefix sum used in order to avoid these calculations and reduce the time complexity by factor O(N).

Follow the steps below to solve the problem:

  • Declare dp[N][Cmax] which has all elements zero initially.
  • Base case  dp[0][0] = 1.
  • Iterate for each 0 to N – 1 on each iteration take prefix sum dp[i][j] = dp[i – 1][j] + dp[i][j – 1];
  • Make values zero that are useless by running a loop from 0 to A[i] and B[i] + 1 to Cmax to avoid calculation errors on the next state.
  • Declare variable ANS and initialize it with value 0.
  • add values for each k from 0 to Cmax of dp[N][k] and print the answer. 

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
// Function to count all possible
// non decreasing arrays
void countNonDecreasingArrays(int A[], int B[], int N)
{
    // Initializing dp table with value 0
    vector<vector<int> > dp(N + 1, vector<int>(3001, 0));
 
    // Base case
    dp[0][0] = 1;
 
    for (int i = 0; i < N; i++) {
 
        // Copying previous value where prefix
        // sum cannot be performed to avoid
        // segmentation fault
        dp[i + 1][0] = dp[i][0];
 
        // Taking prefix sum and improving Naive
        // dp by factor of O(N)
        for (int j = 1; j <= 3000; j++) {
            dp[i + 1][j]
                = (dp[i + 1][j - 1] + dp[i][j]) % MOD;
        }
 
        // Values are only needed from A[i] to B[i]
        // lets make other  values zero
        for (int j = 0; j < A[i]; j++) {
            dp[i + 1][j] = 0;
        }
 
        for (int j = B[i] + 1; j <= 3000; j++) {
            dp[i + 1][j] = 0;
        }
    }
 
    int long long ans = 0;
 
    // Answer will be sum of all dp[N][k]
    // where k is from 0 to 3000
    for (int i = 0; i <= 3000; i++) {
        ans += dp[N][i];
    }
 
    cout << ans % MOD << endl;
}
 
// Driver Code
int main()
{
    // Input 1
    int A[] = { 1, 1 }, B[] = { 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    countNonDecreasingArrays(A, B, N);
 
    // Input 2
    int A1[] = { 2, 2, 2 }, B1[] = { 2, 2, 2 };
    int N1 = sizeof(A1) / sizeof(A1[0]);
 
    // Function Call
    countNonDecreasingArrays(A1, B1, N1);
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
 
class GFG {
    static int MOD = 1000000007;
 
    // Function to count all possible
    // non decreasing arrays
    public static void
    countNonDecreasingArrays(int A[], int B[], int N)
    {
        // Initializing dp table with value 0
        int dp[][] = new int[N + 1][3001];
 
        // Base case
        dp[0][0] = 1;
 
        for (int i = 0; i < N; i++) {
 
            // Copying previous value where prefix
            // sum cannot be performed to avoid
            // segmentation fault
            dp[i + 1][0] = dp[i][0];
 
            // Taking prefix sum and improving Naive
            // dp by factor of O(N)
            for (int j = 1; j <= 3000; j++) {
                dp[i + 1][j]
                    = (dp[i + 1][j - 1] + dp[i][j]) % MOD;
            }
 
            // Values are only needed from A[i] to B[i]
            // lets make other  values zero
            for (int j = 0; j < A[i]; j++) {
                dp[i + 1][j] = 0;
            }
 
            for (int j = B[i] + 1; j <= 3000; j++) {
                dp[i + 1][j] = 0;
            }
        }
 
        long ans = 0;
 
        // Answer will be sum of all dp[N][k]
        // where k is from 0 to 3000
        for (int i = 0; i <= 3000; i++) {
            ans += dp[N][i];
        }
 
        System.out.println(ans % MOD);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Input 1
        int A[] = { 1, 1 };
        int B[] = { 2, 3 };
        int N = A.length;
 
        // Function Call
        countNonDecreasingArrays(A, B, N);
 
        // Input 2
        int A1[] = { 2, 2, 2 };
        int B1[] = { 2, 2, 2 };
        int N1 = A1.length;
 
        // Function Call
        countNonDecreasingArrays(A1, B1, N1);
    }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python code to implement the approach
 
MOD = 1000000007
 
# Function to count all possible
# non decreasing arrays
def countNonDecreasingArrays(A, B, N):
    # Initializing dp table with value 0
    dp = [[0] * 3001 for _ in range(N + 1)]
 
    # Base case
    dp[0][0] = 1
 
    for i in range(N):
        # Copying previous value where prefix
        # sum cannot be performed to avoid
        # segmentation fault
        dp[i + 1][0] = dp[i][0]
 
        # Taking prefix sum and improving Naive
        # dp by factor of O(N)
        for j in range(1, 3001):
            dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j]) % MOD
 
        # Values are only needed from A[i] to B[i]
        # lets make other values zero
        for j in range(A[i]):
            dp[i + 1][j] = 0
 
        for j in range(B[i] + 1, 3001):
            dp[i + 1][j] = 0
 
    ans = 0
 
    # Answer will be sum of all dp[N][k]
    # where k is from 0 to 3000
    for i in range(3001):
        ans += dp[N][i]
 
    print(ans % MOD)
 
# Input 1
A = [1, 1]
B = [2, 3]
N = len(A)
 
# Function Call
countNonDecreasingArrays(A, B, N)
 
# Input 2
A1 = [2, 2, 2]
B1 = [2, 2, 2]
N1 = len(A1)
 
# Function Call
countNonDecreasingArrays(A1, B1, N1)
 
# This code is contributed by lokesh.

C#

// C# code to implement the approach
using System;
 
class GFG {
  static int MOD = 1000000007;
 
  // Function to count all possible
  // non decreasing arrays
  public static void
    countNonDecreasingArrays(int[] A, int[] B, int N)
  {
    // Initializing dp table with value 0
    int[,] dp = new int[N + 1,3001];
 
    // Base case
    dp[0,0] = 1;
 
    for (int i = 0; i < N; i++) {
 
      // Copying previous value where prefix
      // sum cannot be performed to avoid
      // segmentation fault
      dp[i + 1,0] = dp[i,0];
 
      // Taking prefix sum and improving Naive
      // dp by factor of O(N)
      for (int j = 1; j <= 3000; j++) {
        dp[i + 1,j]
          = (dp[i + 1,j - 1] + dp[i,j]) % MOD;
      }
 
      // Values are only needed from A[i] to B[i]
      // lets make other values zero
      for (int j = 0; j < A[i]; j++) {
        dp[i + 1,j] = 0;
      }
 
      for (int j = B[i] + 1; j <= 3000; j++) {
        dp[i + 1,j] = 0;
      }
    }
 
    long ans = 0;
 
    // Answer will be sum of all dp[N,k]
    // where k is from 0 to 3000
    for (int i = 0; i <= 3000; i++) {
      ans += dp[N,i];
    }
 
    Console.WriteLine(ans % MOD);
  }
 
  // Driver Code
  public static void Main()
  {
    // Input 1
    int[] A = { 1, 1 };
    int[] B = { 2, 3 };
    int N = A.Length;
 
    // Function Call
    countNonDecreasingArrays(A, B, N);
 
    // Input 2
    int[] A1 = { 2, 2, 2 };
    int[] B1 = { 2, 2, 2 };
    int N1 = A1.Length;
 
    // Function Call
    countNonDecreasingArrays(A1, B1, N1);
  }
}
 
// This code is contributed by Pushpesh Raj.

Javascript

// JavaScript code to implement the approach
 
let MOD = 1e9 + 7;
 
// Function to count all possible
// non decreasing arrays
function countNonDecreasingArrays( A, B, N)
{
    // Initializing dp table with value 0
    //vector<vector<int> > dp(N + 1, vector<int>(3001, 0));
    let dp=new Array(N+1);
    for(let i=0; i<N+1; i++)
        dp[i]=new Array(3001).fill(0);
 
    // Base case
    dp[0][0] = 1;
 
    for (let i = 0; i < N; i++) {
 
        // Copying previous value where prefix
        // sum cannot be performed to avoid
        // segmentation fault
        dp[i + 1][0] = dp[i][0];
 
        // Taking prefix sum and improving Naive
        // dp by factor of O(N)
        for (let j = 1; j <= 3000; j++) {
            dp[i + 1][j]
                = (dp[i + 1][j - 1] + dp[i][j]) % MOD;
        }
 
        // Values are only needed from A[i] to B[i]
        // lets make other  values zero
        for (let j = 0; j < A[i]; j++) {
            dp[i + 1][j] = 0;
        }
 
        for (let j = B[i] + 1; j <= 3000; j++) {
            dp[i + 1][j] = 0;
        }
    }
 
    let ans = 0;
 
    // Answer will be sum of all dp[N][k]
    // where k is from 0 to 3000
    for (let i = 0; i <= 3000; i++) {
        ans += dp[N][i];
    }
 
    document.write(ans % MOD);
}
 
// Driver Code
    // Input 1
    let A = [ 1, 1 ], B = [ 2, 3 ];
    let N = A.length;
 
    // Function Call
    countNonDecreasingArrays(A, B, N);
     
    document.write("<br>");
 
    // Input 2
    let A1 = [ 2, 2, 2 ], B1 = [ 2, 2, 2 ];
    let N1= A1.length;
    // Function Call
    countNonDecreasingArrays(A1, B1, N1);

Output

5
1

Time Complexity: O(N2)
Auxiliary Space: O(N2)

Another Approach : Using Recursion + memoization

In this approach we solve this problem by calling the function again and again and compute the subproblems to find the solution of actual problem

Implementation steps : 

  • Create a 2d matrix says dp and initialize it with -1.
  • Now recursively call the function for its sub-problems and check in dp whether it is previously computed or not.
  • If it is not computed then dp store -1 and we have to compute the value the store the computed value in dp.
  •  If dp not store -1 then we can say that the current value is previously computed so we will return that value.
  • At last we return the final answer. 

Implementation :

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
// Recursive function to count all possible
// non decreasing arrays
long long countArrays(int A[], int B[], int N, int idx, int prev, vector<vector<long long>>& dp) {
    // Base case
    if (idx == N) {
        return 1;
    }
 
    // If value is already calculated
    if (dp[idx][prev] != -1) {
        return dp[idx][prev];
    }
 
    long long ans = 0;
 
    // Try all possible values for the current index
    for (int i = A[idx]; i <= B[idx]; i++) {
        if (i >= prev) {
            ans += countArrays(A, B, N, idx+1, i, dp);
            ans %= MOD;
        }
    }
 
    // Store the calculated value
    dp[idx][prev] = ans;
 
    return ans;
}
 
// Wrapper function for the recursive function
void countNonDecreasingArrays(int A[], int B[], int N) {
    // Initializing dp table with value -1
    vector<vector<long long>> dp(N, vector<long long>(3001, -1));
 
    // Call the recursive function
    long long ans = countArrays(A, B, N, 0, 0, dp);
 
    cout << ans << endl;
}
 
// Driver Code
int main() {
    // Input 1
    int A[] = { 1, 1 }, B[] = { 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    countNonDecreasingArrays(A, B, N);
 
    // Input 2
    int A1[] = { 2, 2, 2 }, B1[] = { 2, 2, 2 };
    int N1 = sizeof(A1) / sizeof(A1[0]);
 
    // Function Call
    countNonDecreasingArrays(A1, B1, N1);
 
    return 0;
}
 
// this code is contributed by bhardwajji

Java

/*package whatever //do not write package name here */
 
import java.util.*;
 
public class Main {
static final int MOD = 1000000007;
// Recursive function to count all possible
// non decreasing arrays
static long countArrays(int[] A, int[] B, int N, int idx, int prev, long[][] dp) {
    // Base case
    if (idx == N) {
        return 1;
    }
 
    // If value is already calculated
    if (dp[idx][prev] != -1) {
        return dp[idx][prev];
    }
 
    long ans = 0;
 
    // Try all possible values for the current index
    for (int i = A[idx]; i <= B[idx]; i++) {
        if (i >= prev) {
            ans += countArrays(A, B, N, idx+1, i, dp);
            ans %= MOD;
        }
    }
 
    // Store the calculated value
    dp[idx][prev] = ans;
 
    return ans;
}
 
// Wrapper function for the recursive function
static void countNonDecreasingArrays(int[] A, int[] B, int N) {
    // Initializing dp table with value -1
    long[][] dp = new long[N][3001];
    for (long[] row : dp) {
        Arrays.fill(row, -1);
    }
 
    // Call the recursive function
    long ans = countArrays(A, B, N, 0, 0, dp);
 
    System.out.println(ans);
}
 
// Driver Code
public static void main(String[] args) {
    // Input 1
    int[] A = { 1, 1 }, B = { 2, 3 };
    int N = A.length;
 
    // Function Call
    countNonDecreasingArrays(A, B, N);
 
    // Input 2
    int[] A1 = { 2, 2, 2 }, B1 = { 2, 2, 2 };
    int N1 = A1.length;
 
    // Function Call
    countNonDecreasingArrays(A1, B1, N1);
}
}

Python

MOD = 10**9 + 7
 
# Recursive function to count all possible non decreasing arrays
def countArrays(A, B, N, idx, prev, dp):
    # Base case
    if idx == N:
        return 1
 
    # If value is already calculated
    if dp[idx][prev] != -1:
        return dp[idx][prev]
 
    ans = 0
 
    # Try all possible values for the current index
    for i in range(A[idx], B[idx]+1):
        if i >= prev:
            ans += countArrays(A, B, N, idx+1, i, dp)
            ans %= MOD
 
    # Store the calculated value
    dp[idx][prev] = ans
 
    return ans
 
# Wrapper function for the recursive function
def countNonDecreasingArrays(A, B, N):
    # Initializing dp table with value -1
    dp = [[-1 for j in range(3001)] for i in range(N)]
 
    # Call the recursive function
    ans = countArrays(A, B, N, 0, 0, dp)
 
    print(ans)
 
# Driver code
if __name__ == '__main__':
    # Input 1
    A = [1, 1]
    B = [2, 3]
    N = len(A)
 
    # Function call
    countNonDecreasingArrays(A, B, N)
 
    # Input 2
    A1 = [2, 2, 2]
    B1 = [2, 2, 2]
    N1 = len(A1)
 
    # Function call
    countNonDecreasingArrays(A1, B1, N1)
     
 #This code is contributed by Zaid Khan

C#

using System;
using System.Collections.Generic;
 
public class Program {
    const int MOD = 1000000007;
 
    // Recursive function to count all possible
    // non decreasing arrays
    static long CountArrays(int[] A, int[] B, int N, int idx, int prev, long?[,] dp) {
        // Base case
        if (idx == N) {
            return 1;
        }
 
        // If value is already calculated
        if (dp[idx, prev] != null) {
            return dp[idx, prev].Value;
        }
 
        long ans = 0;
 
        // Try all possible values for the current index
        for (int i = A[idx]; i <= B[idx]; i++) {
            if (i >= prev) {
                ans += CountArrays(A, B, N, idx + 1, i, dp);
                ans %= MOD;
            }
        }
 
        // Store the calculated value
        dp[idx, prev] = ans;
 
        return ans;
    }
 
    // Wrapper function for the recursive function
    static void CountNonDecreasingArrays(int[] A, int[] B, int N) {
        // Initializing dp table with value null
        long?[,] dp = new long?[N, 3001];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3001; j++) {
                dp[i, j] = null;
            }
        }
 
        // Call the recursive function
        long ans = CountArrays(A, B, N, 0, 0, dp);
 
        Console.WriteLine(ans);
    }
 
    // Driver Code
    public static void Main() {
        // Input 1
        int[] A = { 1, 1 }, B = { 2, 3 };
        int N = A.Length;
 
        // Function Call
        CountNonDecreasingArrays(A, B, N);
 
        // Input 2
        int[] A1 = { 2, 2, 2 }, B1 = { 2, 2, 2 };
        int N1 = A1.Length;
 
        // Function Call
        CountNonDecreasingArrays(A1, B1, N1);
    }
}

Javascript

// Recursive function to count all possible
// non decreasing arrays
function countArrays(A, B, N, idx, prev, dp) {
    // Base case
    if (idx == N) {
        return 1;
    }
    // If value is already calculated
    if (dp[idx][prev] !== -1) {
        return dp[idx][prev];
    }
 
    let ans = 0;
 
    // Try all possible values for the current index
    for (let i = A[idx]; i <= B[idx]; i++) {
        if (i >= prev) {
            ans += countArrays(A, B, N, idx + 1, i, dp);
            ans %= 1000000007;
        }
    }
 
    // Store the calculated value
    dp[idx][prev] = ans;
 
    return ans;
}
 
// Wrapper function for the recursive function
function countNonDecreasingArrays(A, B, N) {
    // Initializing dp table with value -1
    let dp = Array.from(Array(N), () => new Array(3001).fill(-1));
    // Call the recursive function
    let ans = countArrays(A, B, N, 0, 0, dp);
 
    console.log(ans);
}
 
// Driver Code
// Input 1
let A = [1, 1];
let B = [2, 3];
let N = A.length;
 
// Function Call
countNonDecreasingArrays(A, B, N);
 
// Input 2
let A1 = [2, 2, 2];
let B1 = [2, 2, 2];
let N1 = A1.length;
 
// Function Call
countNonDecreasingArrays(A1, B1, N1);
// This code is contributed by user_dtewbxkn77n

Output

5
1

Time Complexity: O(N2)
Auxiliary Space: O(N2)

Efficient approach : Space optimization

In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.

Implementation: 

C++

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
// Function to count all possible
// non decreasing arrays
void countNonDecreasingArrays(int A[], int B[], int N)
{
    // Initializing dp table with value 0
    vector<int> dp(3001, 0);
 
    // Base case
    dp[0] = 1;
 
    for (int i = 0; i < N; i++) {
 
        // Taking prefix sum and improving Naive
        // dp by factor of O(N)
        for (int j = 1; j <= 3000; j++) {
            dp[j] = (dp[j - 1] + dp[j]) % MOD;
        }
 
        // Values are only needed from A[i] to B[i]
        // lets make other  values zero
        for (int j = 0; j < A[i]; j++) {
            dp[j] = 0;
        }
 
        for (int j = B[i] + 1; j <= 3000; j++) {
            dp[j] = 0;
        }
    }
 
    int long long ans = 0;
 
    // Answer will be sum of all dp[k]
    // where k is from 0 to 3000
    for (int i = 0; i <= 3000; i++) {
        ans += dp[i];
    }
 
    cout << ans % MOD << endl;
}
 
// Driver Code
int main()
{
    // Input 1
    int A[] = { 1, 1 }, B[] = { 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call
    countNonDecreasingArrays(A, B, N);
 
    // Input 2
    int A1[] = { 2, 2, 2 }, B1[] = { 2, 2, 2 };
    int N1 = sizeof(A1) / sizeof(A1[0]);
 
    // Function Call
    countNonDecreasingArrays(A1, B1, N1);
    return 0;
}

Java

import java.util.Arrays;
 
public class CountNonDecreasingArrays {
 
    static final int MOD = 1000000007;
 
    // Function to count all possible non-decreasing arrays
    static void countNonDecreasingArrays(int[] A, int[] B, int N) {
        // Initializing dp table with value 0
        int[] dp = new int[3001];
 
        // Base case
        dp[0] = 1;
 
        for (int i = 0; i < N; i++) {
            // Taking prefix sum and improving the dp array by a factor of O(N)
            for (int j = 1; j <= 3000; j++) {
                dp[j] = (dp[j - 1] + dp[j]) % MOD;
            }
 
            // Values are only needed from A[i] to B[i]
            // Let's make other values zero
            for (int j = 0; j < A[i]; j++) {
                dp[j] = 0;
            }
 
            for (int j = B[i] + 1; j <= 3000; j++) {
                dp[j] = 0;
            }
        }
 
        long ans = 0;
 
        // Answer will be the sum of all dp[k]
        // where k is from 0 to 3000
        for (int i = 0; i <= 3000; i++) {
            ans = (ans + dp[i]) % MOD;
        }
 
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args) {
        // Input 1
        int[] A = {1, 1};
        int[] B = {2, 3};
        int N = A.length;
 
        // Function Call
        countNonDecreasingArrays(A, B, N);
 
        // Input 2
        int[] A1 = {2, 2, 2};
        int[] B1 = {2, 2, 2};
        int N1 = A1.length;
 
        // Function Call
        countNonDecreasingArrays(A1, B1, N1);
    }
}

Python3

# Python program for the above approach
MOD = 10**9 + 7
 
def countNonDecreasingArrays(A, B):
    dp = [0] * 3001  # Initializing dp table with value 0
    dp[0] = 1  # Base case
 
    for i in range(len(A)):
        # Taking prefix sum and improving Naive dp by a factor of O(N)
        for j in range(1, 3001):
            dp[j] = (dp[j - 1] + dp[j]) % MOD
 
        # Values are only needed from A[i] to B[i]
        # Let's make other values zero
        for j in range(A[i]):
            dp[j] = 0
 
        for j in range(B[i] + 1, 3001):
            dp[j] = 0
 
    ans = sum(dp) % MOD  # Answer will be sum of all dp[k] where k is from 0 to 3000
    print(ans)
 
# Driver Code
if __name__ == "__main__":
    # Input 1
    A = [1, 1]
    B = [2, 3]
    countNonDecreasingArrays(A, B)
 
    # Input 2
    A1 = [2, 2, 2]
    B1 = [2, 2, 2]
    countNonDecreasingArrays(A1, B1)

C#

using System;
using System.Collections.Generic;
 
namespace NonDecreasingArrays {
class Program {
    const int MOD = 1000000007;
 
    // Function to count all possible
    // non decreasing arrays
    static void CountNonDecreasingArrays(int[] A, int[] B,
                                         int N)
    {
        // Initializing dp table with value 0
        List<int> dp = new List<int>(new int[3001]);
 
        // Base case
        dp[0] = 1;
 
        for (int i = 0; i < N; i++) {
            // Taking prefix sum and improving Naive
            // dp by factor of O(N)
            for (int j = 1; j <= 3000; j++) {
                dp[j] = (dp[j - 1] + dp[j]) % MOD;
            }
 
            // Values are only needed from A[i] to B[i]
            // lets make other  values zero
            for (int j = 0; j < A[i]; j++) {
                dp[j] = 0;
            }
 
            for (int j = B[i] + 1; j <= 3000; j++) {
                dp[j] = 0;
            }
        }
 
        long ans = 0;
 
        // Answer will be sum of all dp[k]
        // where k is from 0 to 3000
        for (int i = 0; i <= 3000; i++) {
            ans += dp[i];
        }
 
        Console.WriteLine(ans % MOD);
    }
 
    // Driver Code
    static void Main(string[] args)
    {
        // Input 1
        int[] A = { 1, 1 };
        int[] B = { 2, 3 };
        int N = A.Length;
 
        // Function Call
        CountNonDecreasingArrays(A, B, N);
 
        // Input 2
        int[] A1 = { 2, 2, 2 };
        int[] B1 = { 2, 2, 2 };
        int N1 = A1.Length;
 
        // Function Call
        CountNonDecreasingArrays(A1, B1, N1);
    }
}
}

Javascript

// Function to count all possible
// non decreasing arrays
function countNonDecreasingArrays(A, B, N) {
    const MOD = 1e9 + 7;
     
    // Initializing dp table with value 0
    let dp = new Array(3001).fill(0);
     
    // Base case
    dp[0] = 1;
    for (let i = 0; i < N; i++) {
     
        // Taking prefix sum and improving Naive
        // dp by factor of O(N)
        for (let j = 1; j <= 3000; j++) {
            dp[j] = (dp[j - 1] + dp[j]) % MOD;
        }
         
        // Values are only needed from A[i] to B[i]
        // lets make other  values zero
        for (let j = 0; j < A[i]; j++) {
            dp[j] = 0;
        }
        for (let j = B[i] + 1; j <= 3000; j++) {
            dp[j] = 0;
        }
    }
     
    let ans = 0;
     
    // Answer will be sum of all dp[k]
    // where k is from 0 to 3000
    for (let i = 0; i <= 3000; i++) {
        ans += dp[i];
    }
     
    console.log(ans % MOD);
}
 
// Driver Code
 
// Test case 1
let A = [1, 1];
let B = [2, 3];
let N = A.length;
 
countNonDecreasingArrays(A, B, N);
 
// Test case 2
let A1 = [2, 2, 2];
let B1 = [2, 2, 2];
let N1 = A1.length;
 
countNonDecreasingArrays(A1, B1, N1);

Output

5
1

Time Complexity: O(N*3001)
Auxiliary Space: O(3001)

Related Articles:


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Select Minimum indices having sum in first and second Array at least X and Y Select Minimum indices having sum in first and second Array at least X and Y
Minimum cost to reduce given number to less than equal to zero Minimum cost to reduce given number to less than equal to zero
Minimum operations required to Sort the Array using following operations Minimum operations required to Sort the Array using following operations
Implementation of Wu Manber Algorithm? Implementation of Wu Manber Algorithm?
Maximum non overlapping Subset with sum greater than K Maximum non overlapping Subset with sum greater than K

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 10



 

Horje