Count of ways to form 2 necklace from N beads containing N/2 beads each
Given a positive even integer N denoting the number of distinct beads, the task is to find the number of ways to make 2 necklaces having exactly N/2 beads.
Examples:
Input: N = 2
Output: 1
Explanation:
The only possible way to make two necklaces is that {1 | 2}.Input: N = 4
Output: 3
Explanation:
The possible ways to make two necklaces are {(1, 2) | (3, 4)}, {(1, 3) | (2, 4)}, and {(1, 4) | (2, 3)}.
Approach: The problem can be solved by using the concept of circular permutation and combinatorics. Follow the steps below to solve the problem:
- Define a function, say factorial for calculating the factorial of a number, by following the steps below:
- Base Case: If n = 0, then return 1.
- If n != 0, then recursively call the function and return n * factorial(n-1).
- Initialize a variable, say, ans as C(N, N/2), that is the number of ways to choose N/2 beads from N beads.
- Since the necklace is circular, the number of ways to permute N/2 beads are factorial(N/2 -1), so multiply the value of ans by factorial(N/2 -1)*factorial(N/2-1) since there are two necklaces.
- Now divide the ans by 2. Because of symmetrical distribution. For eg, For N=2, the distribution {1 | 2} and {2 | 1} are considered the same.
- Finally, after completing the above steps, print the value of ans as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate factorialint factorial(int n){ if (n == 0) return 1; return n * factorial(n - 1);}// Function to count number of ways// to make 2 necklace having exactly// N/2 beads if each bead is// considered differentlong long numOfNecklace(int N){ // Number of ways to choose N/2 beads // from N beads long long ans = factorial(N) / (factorial(N / 2) * factorial(N / 2)); // Number of ways to permute N/2 beads ans = ans * factorial(N / 2 - 1); ans = ans * factorial(N / 2 - 1); // Divide ans by 2 to remove repetitions ans /= 2; // Return ans return ans;}// Driver Codeint main(){ // Given Input int N = 4; // Function Call cout << numOfNecklace(N) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to calculate factorial static int factorial(int n) { if (n == 0) return 1; return n * factorial(n - 1); } // Function to count number of ways // to make 2 necklace having exactly // N/2 beads if each bead is // considered different static long numOfNecklace(int N) { // Number of ways to choose N/2 beads // from N beads long ans = factorial(N) / (factorial(N / 2) * factorial(N / 2)); // Number of ways to permute N/2 beads ans = ans * factorial(N / 2 - 1); ans = ans * factorial(N / 2 - 1); // Divide ans by 2 to remove repetitions ans /= 2; // Return ans return ans; } // Driver Code public static void main(String[] args) { // Given Input int N = 4; // Function Call System.out.println(numOfNecklace(N)); }}// This code is contributed by Potta Lokesh |
Python3
# Python 3 program for the above approach# Function to calculate factorialdef factorial(n): if (n == 0): return 1 return n * factorial(n - 1)# Function to count number of ways# to make 2 necklace having exactly# N/2 beads if each bead is# considered differentdef numOfNecklace(N): # Number of ways to choose N/2 beads # from N beads ans = factorial(N) // (factorial(N // 2) * factorial(N // 2)) # Number of ways to permute N/2 beads ans = ans * factorial(N // 2 - 1) ans = ans * factorial(N // 2 - 1) # Divide ans by 2 to remove repetitions ans //= 2 # Return ans return ans# Driver Codeif __name__ == '__main__': # Given Input N = 4 # Function Call print(numOfNecklace(N)) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;class GFG{// Function to calculate factorialstatic int factorial(int n){ if (n == 0) return 1; return n * factorial(n - 1);}// Function to count number of ways// to make 2 necklace having exactly// N/2 beads if each bead is// considered differentstatic long numOfNecklace(int N){ // Number of ways to choose N/2 beads // from N beads long ans = factorial(N) / (factorial(N / 2) * factorial(N / 2)); // Number of ways to permute N/2 beads ans = ans * factorial(N / 2 - 1); ans = ans * factorial(N / 2 - 1); // Divide ans by 2 to remove repetitions ans /= 2; // Return ans return ans;}// Driver Codestatic public void Main (){ // Given Input int N = 4; // Function Call Console.Write( numOfNecklace(N));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program for the above approach// Function to calculate factorialfunction factorial(n){ if (n == 0) return 1; return n * factorial(n - 1);}// Function to count number of ways// to make 2 necklace having exactly// N/2 beads if each bead is// considered differentfunction numOfNecklace(N){ // Number of ways to choose N/2 beads // from N beads var ans = factorial(N) / (factorial(N / 2) * factorial(N / 2)); // Number of ways to permute N/2 beads ans = ans * factorial(N / 2 - 1); ans = ans * factorial(N / 2 - 1); // Divide ans by 2 to remove repetitions ans /= 2; // Return ans return ans;}// Driver Code // Given Input var N = 4; // Function Call document.write(numOfNecklace(N));// This code is contributed by SURENDRA_GANGWAR.</script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N), due to recursive call stack
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
