Genere una array con XOR de prefijo de longitud uniforme como 0 o 1

Dado un número entero N , la tarea es construir una array de N elementos distintos ( arr[i] ≤ N+1 ) de modo que el XOR bit a bit de cada prefijo que tenga una longitud par sea 0 o 1 .

Ejemplos:

Entrada: N = 5
Salida = 2 3 4 5 6
Explicación: XOR de arr[1] a arr[2] = XOR(2, 3) = 1
XOR de arr[1] a arr[4] = XOR(2, 3, 4, 5) = 0

Entrada: N = 2
Salida: 2 3

Enfoque: El enfoque del problema se basa en la siguiente observación

2*k XOR (2*k + 1) = 1 donde k ∈ [1, ∞)

La ecuación anterior se puede probar como se muestra a continuación:

• 2k es un número par cuyo LSB es siempre cero. Agregar 1 en esto (dando como resultado 2k+1) cambiará solo un bit del número (LSB se transformará de cero a uno).
• Ahora, 2k y 2k+1 difieren en solo un bit en la posición 0. Entonces, 2*k XOR 2*k+1 = 1 .

Entonces, si se comienza desde k = 1 , y se consideran k consecutivos , las condiciones se cumplirán y todos los prefijos con longitud par tendrán XOR como 1 o 0 (cuando la longitud del prefijo es divisible por 4, porque XOR de número par de 1 será 0)

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

• Declare un vector para almacenar la respuesta.
• Ejecute un ciclo desde   i = 1 hasta n/2 y en cada iteración:
  •  almacenar dos valores en el vector:
    • Primer valor = 2*i .
    • Segundo Valor = 2*i + 1 .
• Si N es impar, inserte el último elemento (N + 1) en el vector porque usando el método anterior solo se puede insertar un número par de elementos.
• Devuelve el vector ya que esta es la array requerida.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to construct the array
vector<int> construct_arr(int n)
{
    vector<int> ans;
    for (int i = 1; i <= n / 2; i++) {
        ans.push_back(2 * i);
        ans.push_back(2 * i + 1);
    }
 
    // If n is odd insert the last element
    if ((n % 2) != 0) {
        ans.push_back(n + 1);
    }
    return ans;
}
 
// Driver code
int main()
{
    int N = 5;
 
    // Function call
    vector<int> ans = construct_arr(N);
 
    // Print the resultant array
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
 
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // Java program for the above approach
 
  // Function to construct the array
  static ArrayList<Integer> construct_arr(int n)
  {
    ArrayList<Integer> ans = new ArrayList<Integer>();
    for (int i = 1; i <= n / 2; i++) {
      ans.add(2*i);
      ans.add(2*i+1);
    }
 
    // If n is odd insert the last element
    if ((n % 2) != 0) {
      ans.add(n + 1);
    }
    return ans;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int N = 5;
 
    // Function call
    ArrayList<Integer> ans = construct_arr(N);
 
    // Print the resultant array
    for (int i = 0; i < ans.size(); i++)
      System.out.print(ans.get(i) + " ");
 
  }
}
 
// This code is contributed by shinjanpatra.

# python code to implement the approach
 
# Function to construct the array
def construct_arr(n):
 
    ans = []
    for i in range(1, n//2+1):
        ans.append(2 * i)
        ans.append(2 * i + 1)
 
    # If n is odd insert the last element
    if ((n % 2) != 0):
        ans.append(n + 1)
 
    return ans
 
 
# Driver code
if __name__ == "__main__":
 
    N = 5
 
    # Function call
    ans = construct_arr(N)
 
    # Print the resultant array
    for i in range(0, len(ans)):
        print(ans[i], end=" ")
 
    # This code is contributed by rakeshsahni

// C# program for the above appraochh
using System;
using System.Collections.Generic;
 
class GFG {
 
  // Function to construct the array
  static List<int> construct_arr(int n)
  {
    List<int> ans = new List<int>();
    for (int i = 1; i <= n / 2; i++) {
      ans.Add(2 * i);
      ans.Add(2 * i + 1);
    }
 
    // If n is odd insert the last element
    if ((n % 2) != 0) {
      ans.Add(n + 1);
    }
    return ans;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 5;
 
    // Function call
    List<int> ans = construct_arr(N);
 
    // Print the resultant array
    for (int i = 0; i < ans.Count; i++)
      Console.Write(ans[i] + " ");
  }
}
 
// This code is contributed by phasing17

<script>
        // JavaScript code for the above approach
 
        // Function to construct the array
        function construct_arr(n) {
            let ans = [];
            for (let i = 1; i <= Math.floor(n / 2); i++) {
                ans.push(2 * i);
                ans.push(2 * i + 1);
            }
 
            // If n is odd insert the last element
            if ((n % 2) != 0) {
                ans.push(n + 1);
            }
            return ans;
        }
 
        // Driver code
 
        let N = 5;
 
        // Function call
        let ans = construct_arr(N);
 
        // Print the resultant array
        for (let i = 0; i < ans.length; i++)
            document.write(ans[i] + " ")
 
    // This code is contributed by Potta Lokesh
    </script>

2 3 4 5 6 

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