Recuento de permutaciones distintas de longitud N que tienen AND bit a bit como cero

Dado un número entero N ., la tarea es encontrar el número de permutaciones distintas de longitud N , de modo que el valor AND bit a bit de cada permutación sea cero . 

Ejemplos:

Entrada: N = 1
Salida: 0 
Explicación: Solo hay una permutación de longitud 1: [1] y es bit a bit AND es 1 . 
 

Entrada: N = 3 
Salida: 6 
Explicación: Las permutaciones de longitud N que tienen AND bit a bit como 0 son: [1, 2, 3], [1, 3, 2], [2, 1, 3], [3, 1, 2], [2, 3, 1], [3, 2, 1] . 

Enfoque:  La tarea se puede resolver usando observaciones. Se puede observar que si un número es una potencia de 2 , digamos ‘ x ‘, AND bit a bit de x & (x-1) es siempre cero. Todas las permutaciones de longitud superior a 1 tienen AND bit a bit como cero , y para N = 1 , el recuento de permutaciones distintas es 0 . Por lo tanto, la cuenta requerida es igual al número de permutaciones posibles, es decir , ¡N!

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

// C++ program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate factorial
// of a number
long long int fact(long long N)
{
    long long int ans = 1;
    for (int i = 2; i <= N; i++)
        ans *= i;
 
    return ans;
}
 
// Function to find distinct no of
// permutations having bitwise and (&)
// equals to 0
long long permutation_count(long long n)
{
    // corner case
    if (n == 1)
        return 0;
 
    return fact(n);
}
 
// Driver code
int main()
{
 
    long long N = 3;
    cout << permutation_count(N);
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG
{
   
  // Function to calculate factorial
// of a number
static long fact( long N)
{
    long  ans = 1;
    for (int i = 2; i <= N; i++)
        ans *= i;
 
    return ans;
}
 
// Function to find distinct no of
// permutations having bitwise and (&)
// equals to 0
static long  permutation_count(long n)
{
   
    // corner case
    if (n == 1)
        return 0;
 
    return fact(n);
}
 
    public static void main (String[] args) {
       long N = 3;
     System.out.println(permutation_count(N));
    }
}
 
// This code is contributed by Potta Lokesh

# Python 3 program for the
# above approach
 
# Function to calculate factorial
# of a number
def fact(N):
 
    ans = 1
    for i in range(2,  N + 1):
        ans *= i
 
    return ans
 
# Function to find distinct no of
# permutations having bitwise and (&)
# equals to 0
def permutation_count(n):
 
    # corner case
    if (n == 1):
        return 0
 
    return fact(n)
 
# Driver code
if __name__ == "__main__":
 
    N = 3
    print(permutation_count(N))
 
    # This code is contributed by ukasp.

// C# program for the
// above approach
using System;
 
class GFG
{
// Function to calculate factorial
// of a number
static long fact(long N)
{
    long ans = 1;
    for (int i = 2; i <= N; i++)
        ans *= i;
 
    return ans;
}
 
// Function to find distinct no of
// permutations having bitwise and (&)
// equals to 0
static long permutation_count(long n)
{
    // corner case
    if (n == 1)
        return 0;
 
    return fact(n);
}
 
// Driver code
public static void Main()
{
 
    long N = 3;
    Console.Write(permutation_count(N));
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
// Javascript program for the
// above approach
 
// Function to calculate factorial
// of a number
function fact(N)
{
    let ans = 1;
    for (let i = 2; i <= N; i++)
        ans *= i;
 
    return ans;
}
 
// Function to find distinct no of
// permutations having bitwise and (&)
// equals to 0
function permutation_count(n)
{
    // corner case
    if (n == 1)
        return 0;
 
    return fact(n);
}
 
// Driver code
let N = 3;
document.write(permutation_count(N));
 
// This code is contributed by Samim Hossain Mondal.
</script>

6

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