Bitwise XOR de todos los números impares de un rango dado

Dado un número entero N , la tarea es encontrar el XOR bit a bit de todos los números impares en el rango [1, N] .

Ejemplos:

Entrada: 11
Salida: 2
Explicación: Bitwise XOR de todos los números impares hasta 11 = 1 ^ 3 ^ 5 ^ 7 ^ 9 ^ 11 = 2.

Entrada: 10
Salida: 9
Explicación: Bitwise XOR de todos los números impares hasta 10 = 1 ^ 3 ^ 5 ^ 7 ^ 9 = 9.

Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar sobre el rango [1, N] y para cada valor, verificar si es impar o no . Calcule Bitwise XOR de cada elemento extraño encontrado e imprímalo como el resultado requerido.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la siguiente fórmula para calcular Bitwise XOR de todos los números impares menores o iguales a N :

Sea f(N) = 2 ^ 4 ^ 6 ^ … ^ (N − 2) ^ n y g(n) = 1 ^ 2 ^ 3 ^ … ^ (N − 2) / 2 ^ (N / 2)
=> f(N) = 2 * g(N)

Ahora, sea k(N) = 1 ^ 2 ^ 3 ^ … ^ (N − 2) ^ N

XOR de todos los números impares menores o iguales a N = k(N) ^ f(N) [Ya que todos los números pares cancelan sus propios bits dejando solo los números impares].
Sustituyendo el valor de f(N) = 2 * g(N), XOR de todos los números impares hasta N = k(N) ^ (2 * g(N))

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

Almacene XOR de números en el rango [1, N] en una variable, digamos K .
Si N es impar , almacene el XOR de números en el rango [1, (N – 1) / 2] en una variable, digamos g . De lo contrario, almacene XOR de números en el rango [1, N / 2] en g .
Usando la fórmula derivada, actualice el resultado a K ^ (2 * g) .
Después de completar los pasos anteriores, imprima el valor del resultado como respuesta.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate Bitwise
// XOR of odd numbers in the range [1, N]
int findXOR(int n)
{
    // N & 3 is equivalent to n % 4
    switch (n & 3) {
 
    // If n is multiple of 4
    case 0:
        return n;
 
    // If n % 4 gives remainder 1
    case 1:
        return 1;
 
    // If n % 4 gives remainder 2
    case 2:
        return n + 1;
 
    // If n % 4 gives remainder 3
    case 3:
        return 0;
    }
}
 
// Function to find the XOR of odd
// numbers less than or equal to N
void findOddXOR(int n)
{
 
    // If number is even
    if (n % 2 == 0)
 
        // Print the answer
        cout << ((findXOR(n))
                 ^ (2 * findXOR(n / 2)));
 
    // If number is odd
    else
 
        // Print the answer
        cout << ((findXOR(n))
                 ^ (2 * findXOR((n - 1) / 2)));
}
 
// Driver Code
int main()
{
    int N = 11;
 
    // Function Call
    findOddXOR(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Function to calculate Bitwise
  // XOR of odd numbers in the range [1, N]
  static int findXOR(int n)
  {
 
    // N & 3 is equivalent to n % 4
    switch (n & 3)
    {
 
        // If n is multiple of 4
      case 0:
        return n;
 
        // If n % 4 gives remainder 1
      case 1:
        return 1;
 
        // If n % 4 gives remainder 2
      case 2:
        return n + 1;
    }
    // If n % 4 gives remainder 3
    return 0;
 
  }
 
  // Function to find the XOR of odd
  // numbers less than or equal to N
  static void findOddXOR(int n)
  {
 
    // If number is even
    if (n % 2 == 0)
 
      // Print the answer
      System.out.print(((findXOR(n))
                        ^ (2 * findXOR(n / 2))));
 
    // If number is odd
    else
 
      // Print the answer
      System.out.print(((findXOR(n))
                        ^ (2 * findXOR((n - 1) / 2))));
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 11;
 
    // Function Call
    findOddXOR(N);
  }
}
 
// This code is contributed by shikhasingrajput

Python3

# Python program for the above approach
 
# Function to calculate Bitwise
# XOR of odd numbers in the range [1, N]
def findXOR(n):
   
    # N & 3 is equivalent to n % 4
    if (n % 4 == 0):
       
        # If n is multiple of 4
        return n;
    elif (n % 4 == 1):
       
        # If n % 4 gives remainder 1
        return 1;
 
    # If n % 4 gives remainder 2
    elif (n % 4 == 2):
        return n + 1;
 
    # If n % 4 gives remainder 3
    elif (n % 4 == 3):
        return 0;
 
# Function to find the XOR of odd
# numbers less than or equal to N
def findOddXOR(n):
   
    # If number is even
    if (n % 2 == 0):
 
        # Print the answer
        print(((findXOR(n)) ^ (2 * findXOR(n // 2))));
 
    # If number is odd
    else:
 
        # Print the answer
        print(((findXOR(n)) ^ (2 * findXOR((n - 1) // 2))));
 
# Driver Code
if __name__ == '__main__':
    N = 11;
 
    # Function Call
    findOddXOR(N);
 
# This code is contributed by 29AjayKumar

C#

// C# program for the above approach
using System;
public class GFG
{
 
  // Function to calculate Bitwise
  // XOR of odd numbers in the range [1, N]
  static int findXOR(int n)
  {
 
    // N & 3 is equivalent to n % 4
    switch (n & 3)
    {
 
        // If n is multiple of 4
      case 0:
        return n;
 
        // If n % 4 gives remainder 1
      case 1:
        return 1;
 
        // If n % 4 gives remainder 2
      case 2:
        return n + 1;
    }
    // If n % 4 gives remainder 3
    return 0;
 
  }
 
  // Function to find the XOR of odd
  // numbers less than or equal to N
  static void findOddXOR(int n)
  {
 
    // If number is even
    if (n % 2 == 0)
 
      // Print the answer
      Console.Write(((findXOR(n))
                     ^ (2 * findXOR(n / 2))));
 
    // If number is odd
    else
 
      // Print the answer
      Console.Write(((findXOR(n))
                     ^ (2 * findXOR((n - 1) / 2))));
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int N = 11;
 
    // Function Call
    findOddXOR(N);
  }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// JavaScript program for the above approach
 
// Function to calculate Bitwise
// XOR of odd numbers in the range [1, N]
function findXOR(n)
{
    // N & 3 is equivalent to n % 4
    switch (n & 3) {
 
    // If n is multiple of 4
    case 0:
        return n;
 
    // If n % 4 gives remainder 1
    case 1:
        return 1;
 
    // If n % 4 gives remainder 2
    case 2:
        return n + 1;
 
    // If n % 4 gives remainder 3
    case 3:
        return 0;
    }
}
 
// Function to find the XOR of odd
// numbers less than or equal to N
function findOddXOR(n)
{
 
    // If number is even
    if (n % 2 == 0)
 
        // Print the answer
        document.write((findXOR(n))
                ^ (2 * findXOR(n / 2)));
 
    // If number is odd
    else
 
        // Print the answer
        document.write((findXOR(n))
                ^ (2 * findXOR((n - 1) / 2)));
}
 
// Driver Code
    let N = 11;
 
    // Function Call
    findOddXOR(N);
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Producción:

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por parthbanathia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta