Dado un número entero par positivo N que denota el número de cuentas distintas, la tarea es encontrar el número de formas de hacer 2 collares que tengan exactamente N/2 cuentas.
Ejemplos:
Entrada: N = 2
Salida: 1
Explicación:
La única forma posible de hacer dos collares es que {1 | 2}.Entrada: N = 4
Salida: 3
Explicación:
Las formas posibles de hacer dos collares son {(1, 2) | (3, 4)}, {(1, 3) | (2, 4)} y {(1, 4) | (2, 3)}.
Enfoque: El problema se puede resolver utilizando el concepto de permutación circular y combinatoria . Siga los pasos a continuación para resolver el problema:
- Defina una función, digamos factorial para calcular el factorial de un número, siguiendo los pasos a continuación:
- Caso base: si n = 0 , devuelve 1 .
- Si n != 0 , llame recursivamente a la función y devuelva n * factorial(n-1) .
- Inicialice una variable, digamos, como C (N, N/2), que es el número de formas de elegir N/2 cuentas de N cuentas.
- Dado que el collar es circular, el número de formas de permutar N/2 cuentas es factorial (N/2 -1), así que multiplique el valor de ans por factorial (N/2 -1)*factorial (N/2-1) ya que hay dos collares.
- Ahora divida el ans por 2. Debido a la distribución simétrica. Por ejemplo, para N=2 , la distribución {1 | 2} y {2 | 1} se consideran iguales.
- Finalmente, después de completar los pasos anteriores, imprima el valor de ans como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate factorial
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
long 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 Code
int main()
{
// Given Input
int N = 4;
// Function Call
cout << numOfNecklace(N) << endl;
return 0;
}
Java
// Java program for the above approach
import 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 factorial def 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 different def 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 Code if __name__ == '__main__': # Given Input N = 4 # Function Call print(numOfNecklace(N)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
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
static 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 factorial
function 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 different
function 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 Cod
// Given Input
var N = 4;
// Function Call
document.write(numOfNecklace(N));
// This code is contributed by SURENDRA_GANGWAR.
</script>
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)