Given two positive numbers ‘n’ and ‘m’ (n <= m) which represent total number of items of first and second type of sets respectively. Find total number of ways to select at-least one pair by picking one item from first type(I) and another item from second type(II). In any arrangement, an item should not be common between any two pairs. Note: Since answer can be large, output it in modulo 1000000007.
Input: 2 2 Output: 6 Explanation Let's denote the items of I type as a, b and II type as c, d i.e, Type I - a, b Type II - c, d Ways to arrange one pair at a time 1. a --- c 2. a --- d 3. b --- c 4. b --- d Ways to arrange two pairs at a time 5. a --- c, b --- d 6. a --- d, b --- c Input: 2 3 Output: 12 Input: 1 2 Output: 2
The approach is simple, we only need the combination of choosing ‘i‘ items from ‘n‘ type and ‘i‘ items from ‘m‘ type and multiply them(Rule of product) where ‘i‘ varies from 1 to ‘n‘. But we can also permute the resultant product in ‘i’ ways therefore we need to multiply with i!. After that take the sum(Rule of sum) of all resultant product to get the final answer.
[Tex]\implies\displaystyle \sum_{i=1}^{\text{n}} \frac{n!}{i!(n-i)!}\cdot \frac{m!}{i!(m-i)!}\cdot i![/Tex]
[Tex]\implies\displaystyle\sum_{i=1}^{\text{n}} \frac{{}^n\text P_i\cdot{}^m\text P_i}{i}[/Tex]
[Tex]\implies\displaystyle \sum_{i=1}^{\text{n}} \frac{n!}{i!(n-i)!}\cdot \frac{m!}{i!(m-i)!}\cdot i![/Tex]
[Tex]\implies\displaystyle\sum_{i=1}^{\text{n}} \frac{{}^n\text P_i\cdot{}^m\text P_i}{i}[/Tex]
C++
// C++ program to find total no. of ways// to form a pair in two different set#include <bits/stdc++.h>using namespace std;// initialize global variable so that// it can access by preCalculate() and// nCr() functionint* fact, *inverseMod;const int mod = 1e9 + 7;/* Iterative Function to calculate (x^y)%p in O(log y) */int power(int x, int y, int p){ int res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y) { // If y is odd, multiply x with result if (y & 1) res = (1LL * res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (1LL * x * x) % p; } // trace(res); return res;}// Pre-calculate factorial and// Inverse of numbervoid preCalculate(int n){ fact[0] = inverseMod[0] = 1; for (int i = 1; i <= n; ++i) { fact[i] = (1LL * fact[i - 1] * i) % mod; inverseMod[i] = power(fact[i], mod - 2, mod); }}// utility function to calculate nCrint nPr(int a, int b){ return (1LL * fact[a] * inverseMod[a - b]) % mod;}int countWays(int n, int m){ fact = new int[m + 1]; inverseMod = new int[m + 1]; // Pre-calculate factorial and // inverse of number preCalculate(m); // Initialize answer int ans = 0; for (int i = 1; i <= n; ++i) { ans += (1LL * ((1LL * nPr(n, i) * nPr(m, i)) % mod) * inverseMod[i]) % mod; if (ans >= mod) ans %= mod; } return ans;}// Driver programint main(){ int n = 2, m = 2; cout << countWays(n, m); return 0;} |
Java
// Java program to find total// no. of ways to form a pair// in two different setpublic class Test{ static long[] fact; static long[] inverseMod; static int mod=1000000007; /* Iterative Function to calculate (x^y)%p in O(log y) */ static long power(long x, int y, int p) { // Initialize result long res = 1; // Update x if it is more than or // equal to p x = x % p; while (y!=0) { // If y is odd, multiply // x with result if ((y & 1)!=0) res = (1 * res * x) % p; } // y must be even now y = y >> 1; x = (1 * x * x) % p; } return res; } // Pre-calculate factorial and // Inverse of number public static void preCalculate(int n) { //int fact[]=new long[n]; // int inverseMod[]=new long[n]; fact[0] = 1; inverseMod[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = (1 * fact[i - 1] * i) % mod; inverseMod[i] = power(fact[i], mod - 2, mod); } } // utility function to calculate nCr public static long nPr(int a, int b) { return (1 * fact[a] * inverseMod[a - b]) % (long)mod; } public static int countWays(int n, int m) { fact = new long[m + 1]; inverseMod = new long[m + 1]; // Pre-calculate factorial and // inverse of number preCalculate(m); // Initialize answer long ans = 0; for (int i = 1; i <= n; i++) { ans = ans+(1 * ((1 * nPr(n, i)* nPr(m, i)) % mod)* (inverseMod[i])) % mod; if (ans >= mod) ans %= mod; } return (int)ans; } /* Driver program */ public static void main(String[] args) { int n = 2, m = 2; System.out.println(countWays(n, m)); }}// This code is contributed by Gitanjali |
Python3
# Python program to find total no. of ways# to form a pair in two different setmod = int(1e9 + 7)# Iterative Function to calculate (x^y)%p in O(log y)def power(x, y, p): res = 1 # Initialize result x = x % p # Update x if it is more than or equal to p while y: # If y is odd, multiply x with result if y & 1: res = (res * x) % p # y must be even now y = y >> 1 # y = y/2 x = (x * x) % p return res# Pre-calculate factorial and Inverse of numberdef preCalculate(n): fact = [0] * (n+1) inverseMod = [0] * (n+1) fact[0], inverseMod[0] = 1, 1 for i in range(1, n+1): fact[i] = (fact[i - 1] * i) % mod inverseMod[i] = power(fact[i], mod - 2, mod) return fact, inverseMod# utility function to calculate nCrdef nPr(a, b, fact, inverseMod): return (fact[a] * inverseMod[a - b]) % moddef countWays(n, m): # Pre-calculate factorial and inverse of number fact, inverseMod = preCalculate(m) # Initialize answer ans = 0 for i in range(1, n+1): ans += (((nPr(n, i, fact, inverseMod) * nPr(m, i, fact, inverseMod)) % mod) * inverseMod[i]) % mod if ans >= mod: ans %= mod return ans# Driver programn = 2m = 2print(countWays(n, m))# This code is contributed by Prince Kumar |
Javascript
// Javascript program for the above approachconst mod = BigInt(1e9 + 7);// Iterative Function to calculate (x^y)%p in O(log y)function power(x, y, p) { let res = BigInt(1); x = x % p; while (y) { if (y & BigInt(1)) { res = (res * x) % p; } y = y >> BigInt(1); x = (x * x) % p; } return res;}// Pre-calculate factorial and Inverse of numberfunction preCalculate(n) { let fact = new Array(n + 1); let inverseMod = new Array(n + 1); fact[0] = inverseMod[0] = BigInt(1); for (let i = 1; i <= n; i++) { fact[i] = (fact[i - 1] * BigInt(i)) % mod; inverseMod[i] = power(fact[i], mod - BigInt(2), mod); } return [fact, inverseMod];}// utility function to calculate nPrfunction nPr(a, b, fact, inverseMod) { return (fact[a] * inverseMod[a - b]) % mod;}function countWays(n, m) { // Pre-calculate factorial and inverse of number const [fact, inverseMod] = preCalculate(m); // Initialize answer let ans = BigInt(0); for (let i = 1; i <= n; i++) { ans += (((nPr(n, i, fact, inverseMod) * nPr(m, i, fact, inverseMod)) % mod) * inverseMod[i]) % mod; if (ans >= mod) { ans %= mod; } } return Number(ans);}const n = 2;const m = 2;console.log(countWays(n, m));// This code is contributed by prince |
C#
// C# program to find total no. of ways// to form a pair in two different setusing System;class Program { static readonly long mod = 1000000007; //Iterative Function to calculate (x^y)%p in O(log y) static long Power(long x, long y, long p) { long res = 1; // Initialize result x %= p; // Update x if it is more than or equal to p // If y is odd, multiply x with result while (y > 0) { if ((y & 1) == 1) { res = (res * x) % p; } // y must be even now y >>= 1; x = (x * x) % p; } return res; } // Pre-calculate factorial and Inverse of number static (long[], long[]) PreCalculate(int n) { long[] fact = new long[n + 1]; long[] inverseMod = new long[n + 1]; fact[0] = inverseMod[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = (fact[i - 1] * i) % mod; inverseMod[i] = Power(fact[i], mod - 2, mod); } return (fact, inverseMod); } // utility function to calculate nCr static long nPr(int a, int b, long[] fact, long[] inverseMod) { return (fact[a] * inverseMod[a - b]) % mod; } static int CountWays(int n, int m) { // Pre-calculate factorial and inverse of number (long[] fact, long[] inverseMod) = PreCalculate(m); // Initialize answer long ans = 0; for (int i = 1; i <= n; i++) { ans += (((nPr(n, i, fact, inverseMod) * nPr(m, i, fact, inverseMod)) % mod) * inverseMod[i]) % mod; if (ans >= mod) { ans %= mod; } } return (int)ans; } // Derive code static void Main(string[] args) { int n = 2; int m = 2; Console.WriteLine(CountWays(n, m)); }}// This code is contributed by Shivhack999 |
Output:
6
Time complexity: O(m*log(mod)) Auxiliary space: O(m) If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
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!