Given 4 numbers N, M, X, Y. which represent N numbers for the first item and M numbers for the second item, the task is to find the number of arrangements of N + M items together such that not more than X first items and not more than Y second items are placed successively.
Examples:
Input: N = 2, M = 1, X = 1, Y = 10
Output: 1
Explanation: Let’s mark the first item as 1
and the second item as 2 the only arrangement possible is 121.Input: N = 2, M = 3, X = 1, Y = 2
Output: 5
Explanation: Lets mark the first element as 1 and second element as 2.
The arrangements possible are 12122, 12212, 21212, 21221, 22121.
Approach: To solve the problem follow the below observations and steps:
There are many possibilities of placing up to X first items and then up to Y second items. So to check each and every possibility we can use dynamic programming.
Since at each step N, M, X, and Y will change so there will be 4 states of dp[] array.
Let the f(n, m, x, y) represents number of ways to choose to make a valid arrangement with x consecutive 1st type elements and y consecutive elements.
So there can be 2 cases: We place first type element: f(n-1, m, x-1, y) or
we choose second type of element: f(n, m-1, x, y-1)So f(n, m, x, y) = f(n – 1, m, x – 1, y) + f(n, m – 1, x, y – 1)
Here is the case that if m or n becomes 0 then on the next iteration we cannot use another consecutive element if 1st or 2nd type.
Follow the below steps to implement the approach:
- Create a recursive function and a 4dimensional array (say dp[]) that will store each of the states.
- Recursively call the functions as mentioned above maintaining the mentioned edge case.
- Return the final value stored at dp[N][M][X][Y] as the required answer.
Below is the implementation of the above approach:
C++14
// C++ code to implement the approach.#include <bits/stdc++.h>using namespace std;// dp arrayint dp[101][101][11][11];// To store original value of X, Yint limit_f = 0, limit_s = 0;// Function to find number of waysint numofways(int n, int m, int x, int y){ // Base case if n1+n2 is 0 that all // items are placed then 1 arrangement // is complete if (n + m == 0) return 1; int f = 0, s = 0; if (dp[n][m][x][y] != -1) // The value is precomputed or not return dp[n][m][x][y]; // If 1st item can be placed if (n > 0 && x > 0) // Since we place the first item // there are limit_s second items // can be placed consecutively f = numofways(n - 1, m, x - 1, limit_s); if (m > 0 && y > 0) // Since we place the second item there // are limit_f first item can be // placed consecutively s = numofways(n, m - 1, limit_f, y - 1); // Total number of arrangements is // addition of 2 return dp[n][m][x][y] = (f + s);}// Driver codeint main(){ int N = 2, M = 3, X = 1, Y = 2; limit_f = X, limit_s = Y; // Initialization for (int i = 0; i <= N; i++) { for (int j = 0; j <= M; j++) { for (int k = 0; k <= X; k++) { for (int m = 0; m <= Y; m++) dp[i][j][k][m] = -1; } } } // Function call cout << numofways(N, M, X, Y) << endl; return 0;} |
Java
// Java code to implement the approach.import java.io.*;class GFG{ // dp array static int dp[][][][] = new int[101][101][11][11]; // To store original value of X, Y static int limit_f = 0, limit_s = 0; // Function to find number of ways public static int numofways(int n, int m, int x, int y) { // Base case if n1+n2 is 0 that all // items are placed then 1 arrangement // is complete if (n + m == 0) return 1; int f = 0, s = 0; if (dp[n][m][x][y] != -1) // The value is precomputed or not return dp[n][m][x][y]; // If 1st item can be placed if (n > 0 && x > 0) // Since we place the first item // there are limit_s second items // can be placed consecutively f = numofways(n - 1, m, x - 1, limit_s); if (m > 0 && y > 0) // Since we place the second item there // are limit_f first item can be // placed consecutively s = numofways(n, m - 1, limit_f, y - 1); // Total number of arrangements is // addition of 2 return dp[n][m][x][y] = (f + s); } // Driver Code public static void main(String[] args) { int N = 2, M = 3, X = 1, Y = 2; limit_f = X; limit_s = Y; // Initialization for (int i = 0; i <= N; i++) { for (int j = 0; j <= M; j++) { for (int k = 0; k <= X; k++) { for (int m = 0; m <= Y; m++) dp[i][j][k][m] = -1; } } } // Function call System.out.println(numofways(N, M, X, Y)); }}// This code is contributed by Rohit Pradhan |
Python3
# dp arraydp = [-1] * 101;for i in range(0, len(dp)): dp[i] = [-1] * 101 for j in range(0,len(dp[i])): dp[i][j] = [-1] * 11 for k in range(0,len(dp[i][j])): dp[i][j][k] = [-1] * 11# To store original value of X, Ylimit_f = 0limit_s = 0# Function to find number of waysdef numofways(n, m, x, y): # Base case if n1+n2 is 0 that all # items are placed then 1 arrangement # is complete if (n + m is 0): return 1 f = 0 s = 0 if (dp[n][m][x][y] != -1): # The value is precomputed or not return dp[n][m][x][y] # If 1st item can be placed if (n > 0 and x > 0): # Since we place the first item # there are limit_s second items # can be placed consecutively f = numofways(n - 1, m, x - 1, limit_s) if (m > 0 and y > 0): # Since we place the second item there # are limit_f first item can be # placed consecutively s = numofways(n, m - 1, limit_f, y - 1) # Total number of arrangements is # addition of 2 dp[n][m][x][y] = (f+s) return dp[n][m][x][y] # Driver codeN = 2M = 3X = 1Y = 2limit_f = Xlimit_s = Y# Initializationfor i in range(0,N+1): for j in range(0,M+1): for k in range(0,X+1): for m in range(0,Y+1): dp[i][j][k][m] = -1# Function callprint(numofways(N, M, X, Y))# This code is contributed by akashish__ |
C#
// C# code to implement the approachusing System;public class GFG{ // dp array public static int [,,,] dp = new int[101,101,11,11]; // To store original value of X, Y public static int limit_f = 0; public static int limit_s = 0; // Function to find number of ways public static int numofways(int n, int m, int x, int y) { // Base case if n1+n2 is 0 that all // items are placed then 1 arrangement // is complete if (n + m == 0) return 1; int f = 0, s = 0; if (dp[n,m,x,y] != -1) // The value is precomputed or not return dp[n,m,x,y]; // If 1st item can be placed if (n > 0 && x > 0) // Since we place the first item // there are limit_s second items // can be placed consecutively f = numofways(n - 1, m, x - 1, limit_s); if (m > 0 && y > 0) // Since we place the second item there // are limit_f first item can be // placed consecutively s = numofways(n, m - 1, limit_f, y - 1); // Total number of arrangements is // addition of 2 return dp[n,m,x,y] = (f + s); } public static void Main(string[] args) { int N = 2, M = 3, X = 1, Y = 2; limit_f = X; limit_s = Y; // Initialization for (int i = 0; i <= N; i++) { for (int j = 0; j <= M; j++) { for (int k = 0; k <= X; k++) { for (int m = 0; m <= Y; m++) dp[i,j,k,m] = -1; } } } // Function call Console.WriteLine(numofways(N, M, X, Y)); }}// This code is contributed by ksam24000 |
Javascript
<script> // JavaScript code for the above approach let dp = new Array(101); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(101); for (let j = 0; j < dp[i].length; j++) { dp[i][j] = new Array(11); for (let k = 0; k < dp[i][j].length; k++) { dp[i][j][k] = new Array(11); } } } // To store original value of X, Y let limit_f = 0, limit_s = 0; // Function to find number of ways function numofways(n, m, x, y) { // Base case if n1+n2 is 0 that all // items are placed then 1 arrangement // is complete if (n + m == 0) return 1; let f = 0, s = 0; if (dp[n][m][x][y] != -1) // The value is precomputed or not return dp[n][m][x][y]; // If 1st item can be placed if (n > 0 && x > 0) // Since we place the first item // there are limit_s second items // can be placed consecutively f = numofways(n - 1, m, x - 1, limit_s); if (m > 0 && y > 0) // Since we place the second item there // are limit_f first item can be // placed consecutively s = numofways(n, m - 1, limit_f, y - 1); // Total number of arrangements is // addition of 2 return dp[n][m][x][y] = (f + s); } // Driver code let N = 2, M = 3, X = 1, Y = 2; limit_f = X, limit_s = Y; // Initialization for (let i = 0; i <= N; i++) { for (let j = 0; j <= M; j++) { for (let k = 0; k <= X; k++) { for (let m = 0; m <= Y; m++) dp[i][j][k][m] = -1; } } } // Function call document.write(numofways(N, M, X, Y));// This code is contributed by Potta Lokesh </script> |
Output
5
Time Complexity: O(N * M * X * Y)
Auxiliary Space: O(N * M * X * Y),
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Below is the implentation of the above approach:
C++
// C++ code to implement the approach.#include <bits/stdc++.h>using namespace std;// Function to find number of waysint numofways(int n, int m, int x, int y){ // dp array int dp[n + 1][m + 1][x + 1][y + 1]; // initialize dp with base cases memset(dp, 0, sizeof(dp)); // Base case initialization for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { for (int k = 0; k <= x; k++) { for (int l = 0; l <= y; l++) { if (i + j == 0) dp[i][j][k][l] = 1; } } } } // iterate over subproblems and get the current // solution for previous computations for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { for (int k = 0; k <= x; k++) { for (int l = 0; l <= y; l++) { if (dp[i][j][k][l] == 0) { int f = 0, s = 0; if (i > 0 && k > 0) f = dp[i - 1][j][k - 1][y]; if (j > 0 && l > 0) s = dp[i][j - 1][x][l - 1]; dp[i][j][k][l] = f + s; } } } } } // return answer return dp[n][m][x][y];}// Driver codeint main(){ int N = 2, M = 3, X = 1, Y = 2; // Function call cout << numofways(N, M, X, Y) << endl; return 0;} |
Python3
def num_of_ways(n, m, x, y): # Initialize dp array with zeros dp = [[[[0 for _ in range(y + 1)] for _ in range(x + 1)] for _ in range(m + 1)] for _ in range(n + 1)] # Base case initialization for i in range(n + 1): for j in range(m + 1): for k in range(x + 1): for l in range(y + 1): if i + j == 0: dp[i][j][k][l] = 1 # Iterate over subproblems and compute the current solution based on previous computations for i in range(n + 1): for j in range(m + 1): for k in range(x + 1): for l in range(y + 1): if dp[i][j][k][l] == 0: f, s = 0, 0 if i > 0 and k > 0: f = dp[i - 1][j][k - 1][y] if j > 0 and l > 0: s = dp[i][j - 1][x][l - 1] dp[i][j][k][l] = f + s # Return the answer return dp[n][m][x][y]# Driver codeif __name__ == "__main__": N, M, X, Y = 2, 3, 1, 2 # Function call print(num_of_ways(N, M, X, Y)) |
Output
5
Time Complexity: O(N * M * X * Y)
Auxiliary Space: O(N * M * X * Y),
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!
