Count of ways N elements can form two different sets containing N/2 elements each
Given a number N, representing count of elements and is equal to 2K, the task is to find the number of ways these elements can be form 2 sets containing K elements each.
Examples:
Input: N = 4
Output: 3
Explanation: The 3 sets consisting of 2 (= N/2) elements are:
[1, 2], [3, 4]
[1, 3], [2, 4]
[1, 4], [2, 3]Input: N = 20
Output: 12164510040883200
Approach: It is to be observed that the concept of combinations has to apply in order to choose the elements for each set.
It is known that the number of ways to choose r things from a total of n things is given by:
nCr = n!/(n-r)!*r!
Now, the above formula can be modified to solve the given problem:
- Here, N/2 elements have to be chosen from N elements to form each set. Hence, r = N/2.
- It is to be noted that the same element cannot be simultaneously present in the two sets. So, the formula of nCr has to be divided by 2.
- Also, the element present in each set can arrange themselves in (N/2-1)! ways. Since there are two sets, the formula will be multiplied by this factor twice.
The modified formula obtained is given by:
Number of ways = ((N! / (N – r)!*r!) / 2) * (N / 2 – 1)!*(N / 2 – 1)! where r = N / 2
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to find the factorial // of values long long int fact( long long int N) { // Factorial of 0 is 1 if (N == 0) { return 1; } else { // Recursive function call return N * fact(N - 1); } } // Driver Code int main() { // Given input int N = 20; // Function Call cout << (fact(N) / (fact(N / 2) * fact(N - N / 2))) / 2 * fact(N / 2 - 1) * fact(N / 2 - 1); return 0; } |
Java
// Java code for the above approach import java.io.*; class GFG { // Function to find the factorial // of values static long fact( long N) { // Factorial of 0 is 1 if (N == 0 ) { return 1 ; } else { // Recursive function call return N * fact(N - 1 ); } } // Driver Code public static void main(String[] args) { // Given input int N = 20 ; // Function Call System.out.println( (fact(N) / (fact(N / 2 ) * fact(N - N / 2 ))) / 2 * fact(N / 2 - 1 ) * fact(N / 2 - 1 )); } } // This code is contributed by Potta Lokesh |
Python3
# python program for the above approach # Function to find the factorial # of values def fact(N): # Factorial of 0 is 1 if (N = = 0 ): return 1 else : # Recursive function call return N * fact(N - 1 ) # Driver Code if __name__ = = "__main__" : # Given input N = 20 # Function Call print ( int ((fact(N) / (fact(N / 2 ) * fact(N - N / 2 ))) / 2 * fact(N / 2 - 1 ) * fact(N / 2 - 1 ))) # This code is contributed by rakeshsahni |
C#
// C# code for the above approach using System; public class GFG { // Function to find the factorial // of values static long fact( long N) { // Factorial of 0 is 1 if (N == 0) { return 1; } else { // Recursive function call return N * fact(N - 1); } } // Driver Code public static void Main( string [] args) { // Given input int N = 20; // Function Call Console.WriteLine( (fact(N) / (fact(N / 2) * fact(N - N / 2))) / 2 * fact(N / 2 - 1) * fact(N / 2 - 1)); } } // This code is contributed AnkThon |
Javascript
<script> // Javascript program for the above approach // Function to find the factorial // of values function fact(N) { // Factorial of 0 is 1 if (N == 0) { return 1; } else { // Recursive function call return N * fact(N - 1); } } // Driver Code // Given input let N = 20; // Function Call document.write((fact(N) / (fact(N / 2) * fact(N - N / 2))) / 2 * fact(N / 2 - 1) * fact(N / 2 - 1)); // This code is contributed by Samim Hossain Mondal. </script> |
12164510040883200
Time Complexity: O(N)
Auxiliary Space: O(N)