Construya una array cuya array Prefijo XOR a partir de X sea una secuencia creciente de longitud N

Dados dos enteros N y X , la tarea es generar una array de tamaño N , de modo que el prefijo x o la array de X con la array generada sean permutaciones de los primeros N números naturales.

Ejemplos: 

Entrada: N = 4, X = 3
Salida: [2, 3, 1, 7]
Explicación:  la array XOR de prefijo para la array {2, 3, 1, 7} es la siguiente:

1. X ⊕ 2 = 1. Ahora, X = 1
2. X ⊕ 3 = 2. Ahora, X = 2
3. X ⊕ 1 = 3. Ahora, X = 3
4. X ⊕ 7 = 4. Ahora, X = 4

La array [1, 2, 3, 4] es una permutación de los primeros 4 números naturales.

Entrada: N = 7, X = 52
Salida: [53, 3, 1, 7, 1, 3, 1]

Enfoque: este problema se puede resolver usando las propiedades de XOR ( si x ⊕ a = b , entonces x ⊕ b = a ). Supongamos que XOR de elementos en la array generada con X hasta el ^índice i es X , y (i + 1) ^el elemento de la array generada es B , entonces B se puede calcular usando los siguientes pasos:

X ⊕ B = i + 1 
Según el enunciado del problema, usando la propiedad de XOR (si x⊕ a = b entonces, x⊕ b = a)… 
X ⊕ i + 1 = B
O
B = X ⊕ i + 1, que es el valor requerido de B .

Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos prev_xor como X .
• Iterar un ciclo usando una variable, digamos i , de 1 a N e imprimir prev_xor ⊕ i .
• Actualice prev_xor como i .

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 print the required array
void GenerateArray(int N, int X)
{
    int prev_xor = X;
 
    // Iterative from 1 to N
    for (int i = 1; i <= N; i++) {
 
        // Print the i-th element
        cout << (i ^ prev_xor);
 
        if (i != N) {
            cout << " ";
        }
 
        // Update prev_xor to i
        prev_xor = i;
    }
}
 
// Driver Code
int main()
{
    // Given Input
    int N = 4, X = 3;
 
    // Function Call
    cout << "The generated array is ";
    GenerateArray(N, X);
    return 0;
}

// Java program for the above approach
class GFG {
 
  // Function to print the required array
  static void GenerateArray(int N, int X)
  {
    int prev_xor = X;
 
    // Iterative from 1 to N
    for (int i = 1; i <= N; i++) {
 
      // Print the i-th element
      System.out.print(i ^ prev_xor);
 
      if (i != N) {
        System.out.print(" ");
      }
 
      // Update prev_xor to i
      prev_xor = i;
    }
  }
 
  // Driver Code
  public static void main(String args[]) {
 
    // Given Input
    int N = 4, X = 3;
 
    // Function Call
    System.out.print("The generated array is ");
    GenerateArray(N, X);
  }
}
 
// This code is contributed by splevel62.

# Python 3 program for the above approach
 
# Function to print the required array
def GenerateArray(N, X):
    prev_xor = X
 
    # Iterative from 1 to N
    for i in range(1,N+1,1):
        # Print the i-th element
        print(i ^ prev_xor,end="")
 
        if (i != N):
            print(" ",end="")
 
        # Update prev_xor to i
        prev_xor = i
 
# Driver Code
if __name__ == '__main__':
    # Given Input
    N = 4
    X = 3
 
    # Function Call
    print("The generated array is ",end="")
    GenerateArray(N, X)
     
    # This code is contributed by ipg2016107

// C# program for above approach
using System;
class GFG
{
 
// Function to print the required array
static void GenerateArray(int N, int X)
{
    int prev_xor = X;
 
    // Iterative from 1 to N
    for (int i = 1; i <= N; i++) {
 
        // Print the i-th element
        Console.Write(i ^ prev_xor);
 
        if (i != N) {
            Console.Write(" ");
        }
 
        // Update prev_xor to i
        prev_xor = i;
    }
}
 
 
// Driver Code
static void Main()
{
   
    // Given Input
    int N = 4, X = 3;
 
    // Function Call
    Console.Write("The generated array is ");
    GenerateArray(N, X);
}
}
 
// This code is contributed by sanjoy_62.

<script>
 
// JavaScript program for the above approach;
 
// Function to print the required array
function GenerateArray(N, X)
{
    let prev_xor = X;
     
    // Iterative from 1 to N
    for(let i = 1; i <= N; i++)
    {
         
        // Print the i-th element
        document.write((i ^ prev_xor));
 
        if (i != N)
        {
            document.write(" ");
        }
 
        // Update prev_xor to i
        prev_xor = i;
    }
}
 
// Driver Code
 
// Given Input
let N = 4, X = 3;
 
// Function Call
document.write("The generated array is ");
GenerateArray(N, X);
 
// This code is contributed by Potta Lokesh
 
</script>

The generated array is 2 3 1 7

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