Cuente las formas de organizar N objetos distintos si todos los arreglos en el sentido de las agujas del reloj se consideran iguales

Dados N objetos distintos, la tarea es encontrar el número de arreglos distintos de N objetos si todos los arreglos en el sentido de las agujas del reloj se consideran iguales.

Si A, B y C son tres objetos distintos, entonces los arreglos {A, B, C}, {C, A, B} y {B, C, A} se consideran iguales, ya que todos los arreglos van en el sentido de las agujas del reloj entre sí. otro.

Ejemplos:

Entrada: N = 3
Salida: 2
Explicación:
La permutación de 3 objetos distintos se puede representar como estos 6 arreglos: {A, B, C}, {A, C, B}, {B, A, C}, {B, C, A}, {C, A, B} y {C, B, A}. Pero los arreglos {A, B, C}, {C, A, B} y {B, C, A} se consideran iguales.
Los arreglos {A, C, B}, {B, A, C} y {C, B, A} también se consideran iguales.
Por lo tanto, solo hay 2 arreglos distintos.

Entrada: N = 2
Salida: 1
Explicación:
Solo pueden haber 2 arreglos: {A, B} y {B, A}. Ambos arreglos son iguales considerando los arreglos en el sentido de las agujas del reloj.
Por lo tanto, solo existe 1 arreglo distinto.

Enfoque ingenuo: la idea es generar toda la permutación de N objetos distintos. Ahora, itere todos los arreglos e incremente el contador si la rotación en el sentido de las agujas del reloj del arreglo actual no está presente en los arreglos anteriores. Después de verificar todos los arreglos, imprima el contador como el total de arreglos distintos en el sentido de las agujas del reloj posibles.

Complejidad de tiempo: O(N*N!)
Espacio auxiliar: O(N*N!) 

Enfoque Eficiente: La idea es utilizar la siguiente observación:

Dada una permutación {A ₁ , A ₂ , …, A _N } de N objetos distintos. Entonces, puede haber N arreglos girados en el sentido de las agujas del reloj que se denotan de la siguiente manera:

{A ₁ , A ₂ , …, A _N }
{A _N , A ₁ , …, A _N-1 }
{A _N-1 , A _N , …, A _N-2 }
{A _N-2 , A _{N -1} , …, A _N-3 }
y así sucesivamente.

Por tanto, para cada permutación de longitud N existen N arreglos en el sentido de las agujas del reloj. Además, para N objetos distintos, ¡hay N! arreglos sin considerar los arreglos en el sentido de las manecillas del reloj iguales.

Por lo tanto, N*X = N!, donde
N son los arreglos en el sentido de las agujas del reloj de cualquier permutación de longitud N.
X es el número de permutaciones considerando iguales los arreglos en el sentido de las agujas del reloj.
¡NORTE! es el número total de permutaciones.

Usando la ecuación anterior:
X = N! / N
X = (N – 1)!

Por lo tanto, el número total de permutaciones distintas considerando los mismos arreglos en el sentido de las agujas del reloj es (N – 1)! . Por lo tanto, la tarea es imprimir el valor del factorial (N – 1) .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to return the factorial
// of given number
unsigned int factorial(unsigned int n)
{
    // Base case
    if (n == 0)
        return 1;
 
    // Recursively find the factorial
    return n * factorial(n - 1);
}
 
// Driver Code
int main()
{
    // Given N objects
    int N = 4;
 
    // Function Call
    cout << factorial(N - 1);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to return the factorial
// of given number
static int factorial(int n)
{
     
    // Base case
    if (n == 0)
        return 1;
 
    // Recursively find the factorial
    return n * factorial(n - 1);
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given N objects
    int N = 4;
 
    // Function Call
    System.out.print(factorial(N - 1));
}
}
 
// This code is contributed by math_lover

# Python3 program for the above approach
 
# Function to return the factorial
# of a given number
def factorial(n):
 
    # Base Case
    if n == 0:
        return 1
     
    # Recursively find the factorial
    return n * factorial(n-1)
 
 
# Driver Code
 
# Given N objects
N = 4
 
# Function Call
print(factorial(N - 1))

// C# program for the
// above approach
using System;
class GFG{
     
// Function to return
// the factorial
// of given number
static int factorial(int n)
{   
  // Base case
  if (n == 0)
    return 1;
 
  // Recursively find the
  // factorial
  return n * factorial(n - 1);
}
 
// Driver Code
public static void Main(String[] args)
{   
  // Given N objects
  int N = 4;
 
  // Function Call
  Console.Write(factorial(N - 1));
}
}
 
// This code is contributed by gauravrajput1

<script>
// Javascript program to implement
// the above approach
 
// Function to return the factorial
// of given number
function factorial(n)
{
      
    // Base case
    if (n == 0)
        return 1;
  
    // Recursively find the factorial
    return n * factorial(n - 1);
}
  
    // Driver Code
     
    // Given N objects
    let N = 4;
  
    // Function Call
    document.write(factorial(N - 1));
           
</script>

6

Complejidad temporal: O(N)
Espacio auxiliar: O(1)