Horje
Count of non decreasing Arrays with ith element in range [A[i], B[i]]

Given two arrays A[] and B[] both consisting of N integers, the task is to find the number of non-decreasing arrays of size N that can be formed such that each array element lies over the range [A[i], B[i]].

Examples:

Input: A[] = {1, 1}, B[] = {2, 3}
Output: 5
Explanation:
The total number of valid arrays are {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}. Therefore, the count of such arrays is 5.

Input: A[] = {3, 4, 5}, B[] = {4, 5, 6}
Output: 8

 

Approach: The given problem can be solved using Dynamic Programming and Prefix Sum. Follow the steps below to solve the problem:

  • Initialize a 2D array dp[][] with values 0, where dp[i][j] denotes the total valid array till position i and with the current element as j. Initialize dp[0][0] as 1.
  • Initialize a 2D array pref[][] with values 0 to store the prefix sum of the array.
  • Iterate over the range [0, B[N – 1]] using the variable i and set the value of pref[0][i] as 1.
  • Iterate over the range [1, N] using the variable i and perform the following steps:
    • Iterate over the range [A[i – 1], B[i – 1]] using the variable j and increment the value of dp[i][j] by pref[i – 1][j] and increase the value of pref[i][j] by dp[i][j].
    • Iterate over the range [0, B[N – 1]] using the variable j and if j is greater than 0 then update the prefix sum table by incrementing the value of pref[i][j] by pref[i][j – 1].
  • Initialize the variable ans as 0 to store the resultant count of arrays formed.
  • Iterate over the range [A[N – 1], B[N – 1]] using the variable i and add the value of dp[N][i] to the variable ans.
  • After performing the above steps, print the value of ans as the answer.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the total number
// of possible valid arrays
int totalValidArrays(int a[], int b[],
                     int N)
{
    // Make a 2D DP table
    int dp[N + 1][b[N - 1] + 1];
 
    // Make a 2D prefix sum table
    int pref[N + 1][b[N - 1] + 1];
 
    // Initialize all values to 0
    memset(dp, 0, sizeof(dp)),
        memset(pref, 0, sizeof(pref));
 
    // Base Case
    dp[0][0] = 1;
 
    // Initialize the prefix values
    for (int i = 0; i <= b[N - 1]; i++) {
        pref[0][i] = 1;
    }
 
    // Iterate over the range and update
    // the dp table accordingly
    for (int i = 1; i <= N; i++) {
        for (int j = a[i - 1];
             j <= b[i - 1]; j++) {
            dp[i][j] += pref[i - 1][j];
 
            // Add the dp values to the
            // prefix sum
            pref[i][j] += dp[i][j];
        }
 
        // Update the prefix sum table
        for (int j = 0; j <= b[N - 1]; j++) {
            if (j > 0) {
                pref[i][j] += pref[i][j - 1];
            }
        }
    }
 
    // Find the result count of
    // arrays formed
    int ans = 0;
    for (int i = a[N - 1];
         i <= b[N - 1]; i++) {
        ans += dp[N][i];
    }
 
    // Return the total count of arrays
    return ans;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 1 };
    int B[] = { 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
 
    cout << totalValidArrays(A, B, N);
 
    return 0;
}

Java

// Java program for the above approach
public class GFG {
     
    // Function to count the total number
    // of possible valid arrays
    static int totalValidArrays(int a[], int b[],
                         int N)
    {
        // Make a 2D DP table
        int dp[][] = new int[N + 1][b[N - 1] + 1];
     
        // Make a 2D prefix sum table
        int pref[][] = new int[N + 1][b[N - 1] + 1];
     
        // Initialize all values to 0
        for (int i = 0; i < N + 1; i++)
            for (int j = 0; j < b[N - 1] + 1; j++)
                dp[i][j] = 0;
                 
        for (int i = 0; i < N + 1; i++)
            for (int j = 0; j < b[N - 1] + 1; j++)
                pref[i][j] = 0;       
 
        // Base Case
        dp[0][0] = 1;
     
        // Initialize the prefix values
        for (int i = 0; i <= b[N - 1]; i++) {
            pref[0][i] = 1;
        }
     
        // Iterate over the range and update
        // the dp table accordingly
        for (int i = 1; i <= N; i++) {
            for (int j = a[i - 1];
                 j <= b[i - 1]; j++) {
                dp[i][j] += pref[i - 1][j];
     
                // Add the dp values to the
                // prefix sum
                pref[i][j] += dp[i][j];
            }
     
            // Update the prefix sum table
            for (int j = 0; j <= b[N - 1]; j++) {
                if (j > 0) {
                    pref[i][j] += pref[i][j - 1];
                }
            }
        }
     
        // Find the result count of
        // arrays formed
        int ans = 0;
        for (int i = a[N - 1];
             i <= b[N - 1]; i++) {
            ans += dp[N][i];
        }
     
        // Return the total count of arrays
        return ans;
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int A[] = { 1, 1 };
        int B[] = { 2, 3 };
        int N = A.length;
     
        System.out.println(totalValidArrays(A, B, N));
    }
}
 
// This code is contributed by AnkThon

Python3

# python program for the above approach
 
# Function to count the total number
# of possible valid arrays
def totalValidArrays(a, b, N):
 
    # Make a 2D DP table
    dp = [[0 for _ in range(b[N - 1] + 1)] for _ in range(N + 1)]
 
    # Make a 2D prefix sum table
    pref = [[0 for _ in range(b[N - 1] + 1)] for _ in range(N + 1)]
 
    # Base Case
    dp[0][0] = 1
 
    # Initialize the prefix values
    for i in range(0, b[N - 1] + 1):
        pref[0][i] = 1
 
    # Iterate over the range and update
    # the dp table accordingly
    for i in range(1, N + 1):
        for j in range(a[i - 1], b[i - 1] + 1):
            dp[i][j] += pref[i - 1][j]
 
            # Add the dp values to the
            # prefix sum
            pref[i][j] += dp[i][j]
 
        # Update the prefix sum table
        for j in range(0, b[N - 1] + 1):
            if (j > 0):
                pref[i][j] += pref[i][j - 1]
 
    # Find the result count of
    # arrays formed
    ans = 0
    for i in range(a[N - 1], b[N - 1] + 1):
        ans += dp[N][i]
 
    # Return the total count of arrays
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    A = [1, 1]
    B = [2, 3]
    N = len(A)
 
    print(totalValidArrays(A, B, N))
 
    # This code is contributed by rakeshsahni

C#

// C#  program for the above approach
using System;
class GFG
{
 
  // Function to count the total number
  // of possible valid arrays
  static int totalValidArrays(int[] a, int[] b, int N)
  {
    // Make a 2D DP table
    int[,] dp = new int[N + 1, b[N - 1] + 1];
 
    // Make a 2D prefix sum table
    int[,] pref = new int[N + 1, b[N - 1] + 1];
 
    // Initialize all values to 0
    for (int i = 0; i < N + 1; i++)
      for (int j = 0; j < b[N - 1] + 1; j++)
        dp[i, j] = 0;
 
    for (int i = 0; i < N + 1; i++)
      for (int j = 0; j < b[N - 1] + 1; j++)
        pref[i, j] = 0;       
 
    // Base Case
    dp[0, 0] = 1;
 
    // Initialize the prefix values
    for (int i = 0; i <= b[N - 1]; i++) {
      pref[0, i] = 1;
    }
 
    // Iterate over the range and update
    // the dp table accordingly
    for (int i = 1; i <= N; i++) {
      for (int j = a[i - 1];
           j <= b[i - 1]; j++) {
        dp[i, j] += pref[i - 1, j];
 
        // Add the dp values to the
        // prefix sum
        pref[i, j] += dp[i, j];
      }
 
      // Update the prefix sum table
      for (int j = 0; j <= b[N - 1]; j++) {
        if (j > 0) {
          pref[i, j] += pref[i, j - 1];
        }
      }
    }
 
    // Find the result count of
    // arrays formed
    int ans = 0;
    for (int i = a[N - 1];
         i <= b[N - 1]; i++) {
      ans += dp[N, i];
    }
 
    // Return the total count of arrays
    return ans;
  }
 
  // Driver Code
  public static void Main ()
  {  
    int[] A = { 1, 1 };
    int[] B = { 2, 3 };
    int N = A.Length;
 
    Console.WriteLine(totalValidArrays(A, B, N));
  }
}
 
// This code is contributed by Saurabh

Javascript

<script>
    // JavaScript program for the above approach
 
    // Function to count the total number
    // of possible valid arrays
    const totalValidArrays = (a, b, N) => {
        // Make a 2D DP table
        let dp = new Array(N + 1).fill(0).map(() => new Array(b[N - 1] + 1).fill(0));
 
        // Make a 2D prefix sum table
        let pref = new Array(N + 1).fill(0).map(() => new Array(b[N - 1] + 1).fill(0));
 
        // Base Case
        dp[0][0] = 1;
 
        // Initialize the prefix values
        for (let i = 0; i <= b[N - 1]; i++) {
            pref[0][i] = 1;
        }
 
        // Iterate over the range and update
        // the dp table accordingly
        for (let i = 1; i <= N; i++) {
            for (let j = a[i - 1];
                j <= b[i - 1]; j++) {
                dp[i][j] += pref[i - 1][j];
 
                // Add the dp values to the
                // prefix sum
                pref[i][j] += dp[i][j];
            }
 
            // Update the prefix sum table
            for (let j = 0; j <= b[N - 1]; j++) {
                if (j > 0) {
                    pref[i][j] += pref[i][j - 1];
                }
            }
        }
 
        // Find the result count of
        // arrays formed
        let ans = 0;
        for (let i = a[N - 1];
            i <= b[N - 1]; i++) {
            ans += dp[N][i];
        }
 
        // Return the total count of arrays
        return ans;
    }
 
    // Driver Code
    let A = [1, 1];
    let B = [2, 3];
    let N = A.length;
 
    document.write(totalValidArrays(A, B, N));
 
// This code is contributed by rakeshsahni
 
</script>

Output: 

5

 

Time Complexity: O(N*M), where M is the last element of the array B[].
Auxiliary Space: O(N*M), where M is the last element of the array B[].


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Lexicographically largest permutation by sequentially inserting Array elements at ends Lexicographically largest permutation by sequentially inserting Array elements at ends
Largest value of K that a set of all possible subset-sum values of given Array contains numbers [0, K] Largest value of K that a set of all possible subset-sum values of given Array contains numbers [0, K]
Minimize cost to modify the Array such that even indices have even elements and vice versa Minimize cost to modify the Array such that even indices have even elements and vice versa
Find the next non-zero Array element to the right of each array element Find the next non-zero Array element to the right of each array element
Minimum and maximum count of elements at D distance from arr[i] in either direction Minimum and maximum count of elements at D distance from arr[i] in either direction

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



 

Horje