Imprima todos los prefijos pares e impares distintos Bitwise XOR de los primeros N números naturales

Dado un entero positivo N , la tarea es imprimir todos los valores pares e impares distintos de los XOR bit a bit de prefijo de los primeros N números naturales .

Ejemplos:

Entrada: N = 6
Salida:
Par: 0 4
Impar: 1 3 7
Explicación:
El prefijo Bitwise XOR de los primeros 6 números naturales si {1, 3, 0, 4, 1, 7}.
Los XOR bit a bit de prefijo par son 0, 4.
Los XOR bit a bit de prefijo impar son 1, 3, 7.

Entrada: N = 9
Salida:
Par: 0 4 8
Impar: 1 3 7

Enfoque: El problema dado se puede resolver en base a las siguientes observaciones:

• Si el valor de N módulo 4 es 0 , entonces el valor de Bitwise XOR de los primeros N números naturales es N.
• Si el valor de N módulo 4 es 1 , entonces el valor de Bitwise XOR de los primeros N números naturales es 1 .
• Si el valor de N módulo 4 es 2 , entonces el valor de Bitwise XOR de los primeros N números naturales es (N + 1) .
• Si el valor de N módulo 4 es 3 , entonces el valor de Bitwise XOR de los primeros N números naturales es 0 .

Por lo tanto, a partir del principio anterior, se puede decir que Bitwise XOR como números pares siempre será 0 o múltiplos de 4 , y Bitwise XOR como números impares siempre será 1 o 1 menos que múltiplos de 4 .

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Print all distinct even & odd
// prefix Bitwise XORs from 1 to N
void evenOddBitwiseXOR(int N)
{
 
    cout << "Even: " << 0 << " ";
 
    // Print the even number
    for (int i = 4; i <= N; i = i + 4) {
        cout << i << " ";
    }
 
    cout << "\n";
 
    cout << "Odd: " << 1 << " ";
 
    // Print the odd number
    for (int i = 4; i <= N; i = i + 4) {
        cout << i - 1 << " ";
    }
 
    if (N % 4 == 2)
        cout << N + 1;
    else if (N % 4 == 3)
        cout << N;
}
 
// Driver Code
int main()
{
    int N = 6;
    evenOddBitwiseXOR(N);
 
    return 0;
}

// Java approach for the above approach
class GFG{
 
// Print all distinct even & odd
// prefix Bitwise XORs from 1 to N
static void evenOddBitwiseXOR(int N)
{
    System.out.print("Even: " + 0 + " ");
 
    // Print the even number
    for(int i = 4; i <= N; i = i + 4)
    {
        System.out.print(i + " ");
    }
 
    System.out.print("\n");
 
    System.out.print("Odd: " + 1 + " ");
 
    // Print the odd number
    for(int i = 4; i <= N; i = i + 4)
    {
        System.out.print(i - 1 + " ");
    }
 
    if (N % 4 == 2)
        System.out.print(N + 1);
    else if (N % 4 == 3)
        System.out.print(N);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 6;
    evenOddBitwiseXOR(N);
}
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Print all distinct even & odd
# prefix Bitwise XORs from 1 to N
def evenOddBitwiseXOR(N):
     
    print("Even: ", 0, end = " ")
 
    # Print the even number
    for i in range(4, N + 1, 4):
        print(i, end = " ")
         
    print()
 
    print("Odd: ", 1, end = " ")
 
    # Print the odd number
    for i in range(4, N + 1, 4):
        print(i - 1, end = " ")
     
    if (N % 4 == 2):
        print(N + 1)
    elif (N % 4 == 3):
        print(N)
 
# Driver Code
N = 6
 
evenOddBitwiseXOR(N)
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
 
class GFG{
     
// Print all distinct even & odd
// prefix Bitwise XORs from 1 to N
static void evenOddBitwiseXOR(int N)
{
    Console.Write("Even: " + 0 + " ");
  
    // Print the even number
    for(int i = 4; i <= N; i = i + 4)
    {
        Console.Write(i + " ");
    }
  
   Console.Write("\n");
  
    Console.Write("Odd: " + 1 + " ");
  
    // Print the odd number
    for(int i = 4; i <= N; i = i + 4)
    {
        Console.Write(i - 1 + " ");
    }
  
    if (N % 4 == 2)
        Console.Write(N + 1);
    else if (N % 4 == 3)
        Console.Write(N);
}
 
// Driver code
public static void Main()
{
    int N = 6;
    evenOddBitwiseXOR(N);
}
}
 
// This code is contributed by splevel62

<script>
 
// Javascript implementation of the above approach
 
// Print all distinct even & odd
// prefix Bitwise XORs from 1 to N
function evenOddBitwiseXOR(N)
{
    document.write("Even: " + 0 + " ");
  
    // Print the even number
    for(let i = 4; i <= N; i = i + 4)
    {
        document.write(i + " ");
    }
  
    document.write("<br/>");
  
    document.write("Odd: " + 1 + " ");
  
    // Print the odd number
    for(let i = 4; i <= N; i = i + 4)
    {
       document.write(i - 1 + " ");
    }
  
    if (N % 4 == 2)
        document.write(N + 1);
    else if (N % 4 == 3)
        document.write(N);
}
 
  
  // Driver Code
     
    let N = 6;
    evenOddBitwiseXOR(N);
     
</script>

Even: 0 4 
Odd: 1 3 7

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