Number of ways to use all the K ropes
Given two walls A, B with M, and N hooks respectively. You are also given K ropes. By using one rope you can connect one hook on wall A with another hook on wall B. One hook can connect with only one rope. Find the number of different ways you can use all the K ropes.
Two ways that use the exact same set of hooks from wall A and wall B are considered to be the same.
For Example,
A1 A2 A3 is the same as A1 A2 A3 and can be ignored.
| | | |
B1 B2 B2 B1
Because both knots are using the same set of wall A hooks (A1, A3) and the same set of wall B hooks (B1, B2)
Note: The answer can be large, return the answer modulo 109+7.
Example:
Input: M = 3, N = 2, K = 2
Output: 3
Explanation: Hooks on Wall A are A1, A2, and A3. The hooks on wall B are B1, and B2.
Different Possible Knots are:
- K1 = (A1-B1, A2-B2), K2 = (A1-B1, A3-B2),
- K3 = (A2-B1, A3-B2)
Each of these uses a different set of hooks from wall A.
Input: M = 2, N = 2, K = 2
Output: 1
Explanation:
A1 A2
| |
B1 B2
There is only one way to select 2 hooks
from wall A and 2 from wall B.
Approach: This can be solved with the following idea:
We must choose K elements from m items by permutation and combination, and the same K elements from n things by combination. The formula for combinatorics will therefore be McK * NcK.
Steps involved in the implementation of code:
- Three integer inputs, M, N, and K, should be used to create the knots function.
- Make a 2D array with a long datatype and Math-sized dimensions.
- initialise all elements to 0, max(M, N)+1.
- Use the formula I choose j) = (i-1 choose j) + (i-1 choose j-1), where I and j are the element’s indices, to set the value of each element in the array to the combination of I and j.
- Comb [i][0] and Comb [i][i] should be set to 1.
- Calculate the result of comb[N][K] and comb[M][K], then place the result in the ans variable.
- Modulate the answer by 1000000007.
Below is the code implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; // Function to calculate // the number of knots int knots( int M, int N, int K) { // Creating a 2D array // of long datatype long long comb[max(M, N) + 1][max(M, N) + 1]; // Loop to fill the 2D array with // the combination values for ( int i = 0; i <= max(M, N); i++) { comb[i][0] = comb[i][i] = 1; for ( int j = 1; j < i; j++) comb[i][j] = ((comb[i - 1][j] % MOD) + (comb[i - 1][j - 1] % MOD)) % MOD; } // Computing the product // of the combinations long long ans = (comb[N][K] * comb[M][K]) % MOD; // Returning the result // modulo 1000000007 return ans; } // Driver code int main() { int M = 2; int N = 2; int K = 2; // Function call int result = knots(M, N, K); cout << result << endl; return 0; } |
Java
/*package whatever // do not write package name here */ import java.util.*; class GFG { static int mod = 1000000007 ; // Function to calculate // the number of knots static int knots( int M, int N, int K) { // Creating a 2D array // of long datatype int x = Math.max(M, N); long [][] comb = new long [x + 1 ][x + 1 ]; // Loop to fill the 2D array with // the combination values for ( int i = 0 ; i <= Math.max(M, N); i++) { comb[i][ 0 ] = comb[i][i] = 1 ; for ( int j = 1 ; j < i; j++) comb[i][j] = ((comb[i - 1 ][j] % mod) + (comb[i - 1 ][j - 1 ] % mod)) % mod; } // Computing the product // of the combinations long ans = (comb[N][K] * comb[M][K]) % mod; // Returning the result // modulo 1000000007 return ( int )ans; } // Driver code public static void main(String[] args) { int M = 2 ; int N = 2 ; int K = 2 ; // Function call int result = knots(M, N, K); System.out.println(result); } } // This code is contributed by ayush pathak |
Python3
MOD = 1000000007 # Function to calculate the number of knots def knots(M, N, K): # Creating a 2D array of long datatype comb = [[ 0 for j in range ( max (M, N) + 1 )] for i in range ( max (M, N) + 1 )] # Loop to fill the 2D array with the combination values for i in range ( max (M, N) + 1 ): comb[i][ 0 ] = comb[i][i] = 1 for j in range ( 1 , i): comb[i][j] = (comb[i - 1 ][j] + comb[i - 1 ][j - 1 ]) % MOD # Computing the product of the combinations ans = (comb[N][K] * comb[M][K]) % MOD # Returning the result modulo 1000000007 return ans # Driver code if __name__ = = '__main__' : M = 2 N = 2 K = 2 # Function call result = knots(M, N, K) print (result) # This code is contributed by rutikbhosale |
C#
using System; public class Program { const int MOD = 1000000007; // Function to calculate // the number of knots public static int Knots( int M, int N, int K) { // Creating a 2D array // of long datatype int x = Math.Max(M, N); long [, ] comb = new long [x + 1, x + 1]; // Loop to fill the 2D array with // the combination values for ( int i = 0; i <= Math.Max(M, N); i++) { comb[i, 0] = comb[i, i] = 1; for ( int j = 1; j < i; j++) { comb[i, j] = ((comb[i - 1, j] % MOD) + (comb[i - 1, j - 1] % MOD)) % MOD; } } // Computing the product // of the combinations long ans = (comb[N, K] * comb[M, K]) % MOD; // Returning the result // modulo 1000000007 return ( int )ans; } // Driver code public static void Main() { int M = 2; int N = 2; int K = 2; // Function call int result = Knots(M, N, K); Console.WriteLine(result); } } // This code is contributed by sarojmcy2e |
Javascript
const MOD = 1000000007; // Function to calculate the number of knots function knots(M, N, K) { // Creating a 2D array of long datatype const comb = new Array(Math.max(M, N) + 1) .fill() .map(() => new Array(Math.max(M, N) + 1).fill(0)); // Loop to fill the 2D array with the combination values for (let i = 0; i <= Math.max(M, N); i++) { comb[i][0] = comb[i][i] = 1; for (let j = 1; j < i; j++) { comb[i][j] = (comb[i - 1][j] % MOD + comb[i - 1][j - 1] % MOD) % MOD; } } // Computing the product of the combinations const ans = (comb[N][K] * comb[M][K]) % MOD; // Returning the result modulo 1000000007 return ans; } // Driver code const M = 2; const N = 2; const K = 2; // Function call const result = knots(M, N, K); console.log(result); |
1
Complexity analysis:
The time complexity of this program is O(max(M,N)^2), where M, N, and K are the inputs to the knots function. The program creates a 2D array of size max(M,N) + 1 x max(M,N) + 1, and fills it with combination values using a nested loop. The outer loop runs max(M,N) times, and the inner loop runs i times, so the total number of iterations is (max(M,N))^2. The rest of the program involves simple arithmetic operations, so it can be considered constant time.
The space complexity of this program is also O(max(M,N)^2), because it creates a 2D array of that size to store the combination values. The rest of the program uses a constant amount of additional space, regardless of the size of the input.
Contact Us