Arrangements of N and M items of two types when max X and Y items of each can be consecutive

19 June 2025

0

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 array
int dp[101][101][11][11];
 
// To store original value of X, Y
int limit_f = 0, limit_s = 0;
 
// Function to find number of ways
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
int 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 array
dp = [-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, Y
limit_f = 0
limit_s = 0
 
# Function to find number of ways
def 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 code
N = 2
M = 3
X = 1
Y = 2
limit_f = X
limit_s = Y
 
# Initialization
for 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 call
print(numofways(N, M, X, Y))
 
# This code is contributed by akashish__

C#

// C# code to implement the approach
using 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

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 ways
int 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 code
int 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 code
if __name__ == "__main__":
    N, M, X, Y = 2, 3, 1, 2
 
    # Function call
    print(num_of_ways(N, M, X, Y))

Output

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!

Arrangements of N and M items of two types when max X and Y items of each can be consecutive

C++14

Java

Python3

C#

Javascript

C++

Python3

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US