Comprobar si el XOR de todos los números en un rango dado es par o impar

Dado un rango [L, R], la tarea es encontrar si el valor de XOR de todos los números naturales en el rango L a R (ambos inclusive) es par o impar. Imprima ‘Par’ si XOR de todos los números en el rango es par, de lo contrario, imprima impar.
Ejemplos: 
 

Input: L = 1, R= 10 
Output: Odd

Input: L= 5, R=15
Output: Even

Una solución simple es calcular XOR de todos los números en el rango [L, R] y luego verificar si el valor XOR resultante es par o impar. 
La complejidad temporal de este enfoque será O(n).
Una solución eficiente se basa en el siguiente hecho: 
 

odd ^ odd = even
odd ^ even = odd
even ^ odd = odd
even ^ even = even

El XOR de todos los números pares será par (independientemente del tamaño del rango) y si el recuento de números impares es impar, el XOR final será impar y, si es par, el XOR final será par.
Ahora bien, se puede concluir que, 
 

• Si el conteo de Números Impares es par, 
  XOR de todos los números impares = Par 
  XOR de todos los números pares = Par 
  XOR Final = Par ^ Par = Par
• Si el conteo de Números Impares es Impar, 
  XOR de todos los números impares = Impar 
  XOR de todos  los números pares = Par XOR
  Final = Impar ^ Par = Impar

Entonces, todo lo que tenemos que hacer es contar los números impares en el rango L a R.
Enfoque: 
 

• Cuente los números impares en el rango [ L, R ].
• Compruebe si el recuento de números impares es par o impar.
• Imprime ‘Par’ si el conteo es par, de lo contrario, imprime ‘Impar’.

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

// C++ program to check if XOR of
// all numbers in range [L, R]
// is Even or odd
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if XOR of all numbers
// in range [L, R] is Even or Odd
 
string isEvenOrOdd(int L, int R)
{
    // Count odd Numbers in range [L, R]
    int oddCount = (R - L) / 2;
 
    if (R % 2 == 1 || L % 2 == 1)
        oddCount++;
 
    // Check if count of odd Numbers
    // is even or odd
 
    if (oddCount % 2 == 0)
        return "Even";
    else
        return "Odd";
}
 
// Driver Code
int main()
{
 
    int L = 5, R = 15;
 
    cout << isEvenOrOdd(L, R);
 
    return 0;
}

// Java program to check if XOR of
// all numbers in range [L, R]
// is Even or odd
 
class GFG {
 
    // Function to check if XOR of all numbers
    // in range [L, R] is Even or Odd
 
    static String isEvenOrOdd(int L, int R)
    {
        // Count odd Numbers in range [L, R]
        int oddCount = (R - L) / 2;
 
        if (R % 2 == 1 || L % 2 == 1)
            oddCount++;
 
        // Check if count of odd Numbers
        // is even or odd
 
        if (oddCount % 2 == 0)
            return "Even";
        else
            return "Odd";
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int L = 5, R = 15;
 
        System.out.println(isEvenOrOdd(L, R));
    }
}

// C# program to check if XOR of
// all numbers in range [L, R]
// is Even or odd
 
using System;
class GFG {
 
    // Function to check if XOR of all numbers
    // in range [L, R] is Even or Odd
 
    static string isEvenOrOdd(int L, int R)
    {
        // Count odd Numbers in range [L, R]
        int oddCount = (R - L) / 2;
 
        if (R % 2 == 1 || L % 2 == 1)
            oddCount++;
 
        // Check if count of odd Numbers
        // is even or odd
 
        if (oddCount % 2 == 0)
            return "Even";
        else
            return "Odd";
    }
 
    // Driver Code
    public static void Main()
    {
 
        int L = 5, R = 15;
 
        Console.WriteLine(isEvenOrOdd(L, R));
    }
}

# Python3 program to check if XOR of
# all numbers in range [L, R]
# is Even or odd
 
 
# Function to check if XOR of all numbers
# in range [L, R] is Even or Odd
 
def isEvenOrOdd( L, R ):
 
    # Count odd Numbers in range [L, R]
    oddCount = (R - L )/2
     
    if( R % 2 == 1 or L % 2 == 1):
        oddCount = oddCount + 1
     
     
    # Check if count of odd Numbers
    # is even or odd
     
    if(oddCount % 2 == 0 ):
        return "Even"
    else :
        return "Odd"
         
 
     
# Driver Code
 
L = 5
R = 15
 
print(isEvenOrOdd(L, R));

<?php
// PHP program to check if XOR of all
// numbers in range [L, R] is Even or odd
 
// Function to check if XOR of all numbers
// in range [L, R] is Even or Odd
function isEvenOrOdd($L, $R)
{
    // Count odd Numbers in range [L, R]
    $oddCount = floor(($R - $L) / 2);
 
    if ($R % 2 == 1 || $L % 2 == 1)
        $oddCount++;
 
    // Check if count of odd Numbers
    // is even or odd
    if ($oddCount % 2 == 0)
        return "Even";
    else
        return "Odd";
}
 
// Driver Code
$L = 5;
$R = 15;
 
echo isEvenOrOdd($L, $R);
 
// This code is contributed by Ryuga
?>

<script>
// JavaScript program to check if XOR of
// all numbers in range [L, R]
// is Even or odd
 
 
// Function to check if XOR of all numbers
// in range [L, R] is Even or Odd
 
function isEvenOrOdd(L, R)
{
    // Count odd Numbers in range [L, R]
    let oddCount = Math.floor((R - L) / 2);
 
    if (R % 2 == 1 || L % 2 == 1)
        oddCount++;
 
    // Check if count of odd Numbers
    // is even or odd
 
    if (oddCount % 2 == 0)
        return "Even";
    else
        return "Odd";
}
 
// Driver Code
 
    let L = 5, R = 15;
 
    document.write(isEvenOrOdd(L, R));
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Even

Complejidad temporal: O(1), ya que no hay bucle ni recursividad.
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.