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 arraysint 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 Codeint 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 approachpublic 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 arraysdef 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 Codeif __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 approachusing 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[].
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
