Recuento de permutaciones con el mínimo posible XOR máximo de pares adyacentes

Dado un número entero N , considere una array que tenga elementos en el rango [0, N-1] de modo que el XOR bit a bit máximo de todos los pares adyacentes sea el mínimo de todas las permutaciones posibles de la array. Encuentre el número de tales permutaciones.

Ejemplos:

Entrada: N = 3
Salida: 2
Explicación: 
A[] = {2, 0, 1}, el máximo de XOR(2, 0) y XOR(0, 1) es 2
A[] = {1, 0, 2} , El máximo de XOR(1, 0) y XOR(0, 2) es 2
Todas las demás permutaciones de la array tienen un XOR máximo mayor que
2, por lo tanto, las dos anteriores son las únicas permutaciones con el XOR mínimo.

Entrada: N = 5
Salida: 12
Explicación: Las permutaciones son:
{1, 2, 3, 0, 4}, {1, 3, 2, 0, 4}, {2, 1, 3, 0, 4}, {3, 2, 1, 0, 4}, {3, 1, 2, 0, 4}, {2, 3, 1, 0, 4}, 
{4, 0, 1, 2, 3}, {4 , 0, 1, 3, 2}, {4, 0, 2, 3, 1}, {4, 0, 2, 1, 3}, {4, 0, 3, 1, 2}, {4, 0 , 3, 2, 1}.
Todas estas permutaciones tienen un valor máximo de XOR como 4, que es el mínimo posible.

Enfoque: si todos los elementos se escriben en sus representaciones binarias, se pueden dividir en dos grupos en función de la condición de que tenga el conjunto de bits más a la izquierda posible . Entonces, un grupo tendrá elementos con el conjunto de bits máximo a la izquierda posible y el otro contendrá los elementos restantes. La siguiente es la observación principal para resolver el problema:

• La observación clave aquí es que el XOR máximo ocurrirá cuando los pares adyacentes sean de dos grupos diferentes ,
• Entonces, para minimizar el máximo, la permutación debe ser tal que solo haya un par adyacente cuyos elementos sean de diferentes grupos y ese par clave consistirá en 0 y la potencia integral más alta de 2 antes de N . Como la potencia de 2 tendrá solo 1 bit configurado en comparación con todos los números enteros mayores que él y 0, por supuesto, no tiene conjunto de bits, forman el par óptimo perfecto.
• Los elementos del mismo grupo permanecerán en el mismo lado del par de claves , es decir, los elementos con los bits más significativos establecidos permanecerán en el lado de mayor potencia integral de 2 y los demás en el lado opuesto.
• La respuesta final = número de permutaciones a la izquierda del par de claves * número de permutaciones a la derecha del par de claves * 2 .

Siga los pasos mencionados a continuación para implementar la observación anterior:

• Encuentre el setbit más a la izquierda máximo posible .
• Ahora cuente el número de elementos en cada grupo .
• Encuentra el par de claves .
• Cuente las permutaciones en cada lado y multiplíquelas entre sí y 2 .
• Devuelve este valor multiplicado como la respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find factorial of a number
int factorial(int x)
{
    int ans = 1;
    while (x > 0) {
        ans = ans * x;
        x--;
    }
    return ans;
}
 
// Function to find the MSB of a number
int mostSigBit(int x)
{
    int msb = -1;
    while (x != 0) {
        x = x >> 1;
        msb++;
    }
    return msb;
}
 
// Function to calculate number of possible
// permutations with minimum bitwise XOR
int minXor(int N)
{
    int highest_bit = mostSigBit(N - 1);
 
    // The highest power of 2 before
    // the largest number which will
    // be part of the key pair with 0
    int key = 1 << highest_bit;
 
    // Count of elements in group 1
    int grp1 = 0;
 
    // Count of elements in group 2
    int grp2 = 0;
 
    for (int i = 1; i < N; i++) {
        if (i > key)
            grp2++;
        else if (i < key)
            grp1++;
    }
 
    int ans = (factorial(grp1)
               * factorial(grp2))
              * 2;
    return ans;
}
 
// Driver code
int main()
{
    int N = 5;
 
    // Function call
    int ans = minXor(N);
    cout << ans;
    return 0;
}

// Java program for the above approach
import java.util.*;
 
public class GFG {
 
    // Function to find factorial of a number
    static int factorial(int x)
    {
        int ans = 1;
        while (x > 0) {
            ans = ans * x;
            x--;
        }
        return ans;
    }
 
    // Function to find the MSB of a number
    static int mostSigBit(int x)
    {
        int msb = -1;
        while (x != 0) {
            x = x >> 1;
            msb++;
        }
        return msb;
    }
 
    // Function to calculate number of possible
    // permutations with minimum bitwise XOR
    static int minXor(int N)
    {
        int highest_bit = mostSigBit(N - 1);
 
        // The highest power of 2 before the
        // largest number which will be
        // part of the key pair with 0
        int key = 1 << highest_bit;
 
        // Count of elements in group 1
        int grp1 = 0;
 
        // Count of elements in group 2
        int grp2 = 0;
 
        for (int i = 1; i < N; i++) {
            if (i > key)
                grp2++;
            else if (i < key)
                grp1++;
        }
 
        int ans = (factorial(grp1)
                   * factorial(grp2))
                  * 2;
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 5;
 
        // Function call
        int ans = minXor(N);
        System.out.println(ans);
    }
}

# Python code for the above approach
 
# Function to find factorial of a number
def factorial(x):
    ans = 1;
    while (x > 0):
        ans = ans * x;
        x -= 1
 
    return ans;
 
# Function to find the MSB of a number
def mostSigBit(x):
    msb = -1;
    while (x != 0):
        x = x >> 1;
        msb += 1
     
    return msb;
 
# Function to calculate number of possible
# permutations with minimum bitwise XOR
def minXor(N):
    highest_bit = mostSigBit(N - 1);
 
    # The highest power of 2 before
    # the largest number which will
    # be part of the key pair with 0
    key = 1 << highest_bit;
 
    # Count of elements in group 1
    grp1 = 0;
 
    # Count of elements in group 2
    grp2 = 0;
 
    for i in range(1, N) :
        if (i > key):
            grp2 += 1
        elif (i < key):
            grp1 += 1
     
    ans = (factorial(grp1) * factorial(grp2)) * 2
    return ans;
 
# Driver code
N = 5;
 
# Function call
ans = minXor(N);
print(ans);
 
# This code is contributed by Saurabh jaiswal

// C# program for the above approach
using System;
class GFG {
 
  // Function to find factorial of a number
  static int factorial(int x)
  {
    int ans = 1;
    while (x > 0) {
      ans = ans * x;
      x--;
    }
    return ans;
  }
 
  // Function to find the MSB of a number
  static int mostSigBit(int x)
  {
    int msb = -1;
    while (x != 0) {
      x = x >> 1;
      msb++;
    }
    return msb;
  }
 
  // Function to calculate number of possible
  // permutations with minimum bitwise XOR
  static int minXor(int N)
  {
    int highest_bit = mostSigBit(N - 1);
 
    // The highest power of 2 before the
    // largest number which will be
    // part of the key pair with 0
    int key = 1 << highest_bit;
 
    // Count of elements in group 1
    int grp1 = 0;
 
    // Count of elements in group 2
    int grp2 = 0;
 
    for (int i = 1; i < N; i++) {
      if (i > key)
        grp2++;
      else if (i < key)
        grp1++;
    }
 
    int ans = (factorial(grp1)
               * factorial(grp2))
      * 2;
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int N = 5;
 
    // Function call
    int ans = minXor(N);
    Console.WriteLine(ans);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to find factorial of a number
       function factorial(x) {
           let ans = 1;
           while (x > 0) {
               ans = ans * x;
               x--;
           }
           return ans;
       }
 
       // Function to find the MSB of a number
       function mostSigBit(x) {
           let msb = -1;
           while (x != 0) {
               x = x >> 1;
               msb++;
           }
           return msb;
       }
 
       // Function to calculate number of possible
       // permutations with minimum bitwise XOR
       function minXor(N) {
           let highest_bit = mostSigBit(N - 1);
 
           // The highest power of 2 before
           // the largest number which will
           // be part of the key pair with 0
           let key = 1 << highest_bit;
 
           // Count of elements in group 1
           let grp1 = 0;
 
           // Count of elements in group 2
           let grp2 = 0;
 
           for (let i = 1; i < N; i++) {
               if (i > key)
                   grp2++;
               else if (i < key)
                   grp1++;
           }
 
           let ans = (factorial(grp1)
               * factorial(grp2))
               * 2;
           return ans;
       }
 
       // Driver code
       let N = 5;
 
       // Function call
       let ans = minXor(N);
       document.write(ans);
 
      // This code is contributed by Potta Lokesh
   </script>

12

 Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)