Given two array of size n and m. The task is to find the number of ways we can merge the given arrays into one array such that order of elements of each array doesn’t change.
Examples:
Input : n = 2, m = 2 Output : 6 Let first array of size n = 2 be [1, 2] and second array of size m = 2 be [3, 4]. So, possible merged array of n + m elements can be: [1, 2, 3, 4] [1, 3, 2, 4] [3, 4, 1, 2] [3, 1, 4, 2] [1, 3, 4, 2] [3, 1, 2, 4] Input : n = 4, m = 6 Output : 210
The idea is to use the concept of combinatorics. Suppose we have two array A{a1, a2, …., am} and B{b1, b2, …., bn} having m and n elements respectively and now we have to merge them without losing their order.
After merging we know that the total number of element will be (m + n) element after merging. So, now we just need the ways to choose m places out of (m + n) where you will place element of array A in its actual order, which is m + nCn.
After placing m element of array A, n spaces will be left, which can be filled by the n elements of B array in its actual order.
So, total number of ways to merge two array such that their order in merged array is same is m + nCn
Below is the implementation of this approach:
C++
// CPP Program to find number of ways// to merge two array such that their // order in merged array is same#include <bits/stdc++.h>using namespace std;// function to find the binomial coefficientint binomialCoeff(int n, int k){ int C[k + 1]; memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for (int i = 1; i <= n; i++) { // Compute next row of pascal triangle // using the previous row for (int j = min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k];}// function to find number of ways // to merge two array such that their // order in merged array is sameint numOfWays(int n, int m){ return binomialCoeff(m + n, m);}// Driven Programint main(){ int n = 2, m = 2; cout << numOfWays(n, m) << endl; return 0;} |
Java
// Java Program to find number of ways// to merge two array such that their // order in merged array is sameimport java.io.*;class GFG { // function to find the binomial // coefficient static int binomialCoeff(int n, int k) { int C[] = new int[k + 1]; // memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for (int i = 1; i <= n; i++) { // Compute next row of pascal // triangle using the previous // row for (int j = Math.min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k]; } // function to find number of ways // to merge two array such that their // order in merged array is same static int numOfWays(int n, int m) { return binomialCoeff(m + n, m); } // Driven Program public static void main (String[] args) { int n = 2, m = 2; System.out.println(numOfWays(n, m)); }}// This code is contributed by anuj_67. |
Python3
# Python 3 Program to find number of ways# to merge two array such that their # order in merged array is same# function to find the binomial coefficientdef binomialCoeff(n, k): C = [0 for i in range(k + 1)] C[0] = 1 for i in range(1, n + 1, 1): # Compute next row of pascal # triangle using the previous row j = min(i, k) while(j > 0): C[j] = C[j] + C[j - 1] j -= 1 return C[k]# function to find number of ways # to merge two array such that their # order in merged array is samedef numOfWays(n, m): return binomialCoeff(m + n, m)# Driver Codeif __name__ == '__main__': n = 2 m = 2 print(numOfWays(n, m)) # This code is contributed by# Sahil_shelangia |
C#
// C# Program to find number of ways// to merge two array such that their // order in merged array is sameusing System;class GFG { // function to find the binomial // coefficient static int binomialCoeff(int n, int k) { int []C = new int[k + 1]; // memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for (int i = 1; i <= n; i++) { // Compute next row of pascal // triangle using the previous // row for (int j = Math.Min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k]; } // function to find number of ways // to merge two array such that their // order in merged array is same static int numOfWays(int n, int m) { return binomialCoeff(m + n, m); } // Driven Program public static void Main () { int n = 2, m = 2; Console.WriteLine(numOfWays(n, m)); }}// This code is contributed by anuj_67. |
PHP
<?php// PHP Program to find number of ways // to merge two array such that their // order in merged array is same // function to find the binomial coefficient function binomialCoeff($n, $k) { $C = array($k + 1); for($i=0; $i < count($C); $i++) $C[$i] = 0; $C[0] = 1; // nC0 is 1 for ( $i = 1; $i <= $n; $i++) { // Compute next row of pascal triangle // using the previous row for ( $j = min($i, $k); $j > 0; $j--) $C[$j] = $C[$j] + $C[$j - 1 ]; } return $C[$k]; } // function to find number of ways // to merge two array such that their // order in merged array is same function numOfWays( $n, $m) { return binomialCoeff($m + $n, $m); } $n = 2; $m = 2; echo numOfWays($n, $m); //This code is contributed by Rajput-Ji.?> |
Javascript
<script> // Javascript Program to find number of ways // to merge two array such that their // order in merged array is same // function to find the binomial // coefficient function binomialCoeff(n, k) { let C = new Array(k + 1); C.fill(0); // memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for (let i = 1; i <= n; i++) { // Compute next row of pascal // triangle using the previous // row for (let j = Math.min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k]; } // function to find number of ways // to merge two array such that their // order in merged array is same function numOfWays(n, m) { return binomialCoeff(m + n, m); } let n = 2, m = 2; document.write(numOfWays(n, m)); // This code is contributed by divyeshrabadiya07.</script> |
Output
6
Time Complexity: O((m+n)*m)
Auxiliary Space: O(m)
We can solve above problem in linear time using linear time implementation of binomial coefficient.
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!
