Cuente los XOR bit a bit pares e impares de números consecutivos en un rango [L, R] a partir de L

Dados dos números enteros L y R , la tarea es encontrar el recuento de valores XOR bit a bit pares e impares de números consecutivos del rango [L, R] a partir de L .

Ejemplos:

Entrada: L = 2, R = 7
Salida: Par = 3, Impar = 3
Explicación: Tomando XOR bit a bit de números continuos:
2
2 ^ 3 = 1
2 ^ 3 ^ 4 = 5
2 ^ 3 ^ 4 ^ 5 = 0
2 ^ 3 ^ 4 ^ 5 ^ 6 = 6
2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 1
Por lo tanto, los valores Bitwise XOR obtenidos son {2, 1, 5, 0, 6, 1}.
Por lo tanto, el recuento de valores XOR pares es 3 y los valores XOR impares son 3.

Entrada: L = 1, R = 7
Salida: Par = 3, Impar = 4

Enfoque ingenuo: el enfoque más simple es atravesar todos los números en el rango [L, R] y realizar Bitwise XOR de números consecutivos a partir de L . Finalmente, cuente el número de valores pares e impares Bitwise XOR obtenidos. 
Complejidad temporal: O(R – L)
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en la siguiente observación de que el XOR bit a bit de 1 a N se puede calcular en tiempo constante:

• Encuentra el resto de N cuando se divide por 4.
• Si el resto obtenido es 0 , entonces XOR será igual a N.
• Si el resto obtenido es 1 , entonces XOR será igual a 1 .
• Si el resto obtenido es 2 , entonces XOR será igual a N + 1 .
• Si el resto obtenido es 3 , entonces el XOR obtenido será 0 .

De la observación anterior, se puede concluir que los valores XOR pares son 0 o múltiplos de 4. Siga los pasos a continuación para resolver el problema:

• Almacene la cantidad de elementos en el rango [L, R] en una variable, digamos X .
• Almacene el recuento de valores XOR pares dividiendo X por 4 y multiplicando por 2 en una variable, digamos Even .
• Si L es impar y X % 4 es igual a 3 , entonces incremente Even en 1 .
• De lo contrario, si L es par y X % 4 es mayor que 0 , entonces incremente Even en 1 .
• Almacene el recuento de valores impares de XOR en una variable Impar = X – Par .
• Después de completar los pasos anteriores, imprima el valor de Par e Impar como resultado.

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 count of even and odd numbers
// of XOR value from L to R
void countEvenOdd(int L, int R)
{
    // Store the number of elements
    // between L and R
    int range = R - L + 1;
 
    // Count of even XOR values
    int even = (range / 4) * 2;
 
    // If L is odd and range % 4 = 3
    if ((L & 1) && (range % 4 == 3)) {
 
        // Increment even by 1
        even++;
    }
 
    // If L is even and range % 4 !=0
    else if (!(L & 1) && (range % 4)) {
 
        // Increment even by 1
        even++;
    }
 
    // Print the answer
    cout << "Even = " << even
         << ", Odd = " << range - even;
}
 
// Driver Code
int main()
{
    int L = 2, R = 7;
    countEvenOdd(L, R);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
  // Print count of even and odd numbers
  // of XOR value from L to R
  static void countEvenOdd(int L, int R)
  {
 
    // Store the number of elements
    // between L and R
    int range = R - L + 1;
 
    // Count of even XOR values
    int even = (range / 4) * 2;
 
    // If L is odd and range % 4 = 3
    if ((L & 1) != 0 && (range % 4 == 3))
    {
 
      // Increment even by 1
      even++;
    }
 
    // If L is even and range % 4 !=0
    else if ((L & 1) == 0 && (range % 4 != 0))
    {
 
      // Increment even by 1
      even++;
    }
 
    // Print the answer
    System.out.print("Even = " + even +
                     ", Odd = " + (range - even));
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int L = 2, R = 7;
    countEvenOdd(L, R);
  }
}
 
// This code is contributed by sanjoy_62.

# Python program for the above approach
 
# Print count of even and odd numbers
# of XOR value from L to R
def countEvenOdd(L, R):
   
    # Store the number of elements
    # between L and R
    range = R - L + 1;
 
    # Count of even XOR values
    even = (range // 4) * 2;
 
    # If L is odd and range % 4 = 3
    if ((L & 1) != 0 and (range % 4 == 3)):
 
        # Increment even by 1
        even += 1;
 
    # If L is even and range % 4 !=0
    elif ((L & 1) == 0 and (range % 4 != 0)):
 
        # Increment even by 1
        even += 1;
 
    # Print the answer
    print("Even = " , even ,\
          ", Odd = " , (range - even));
 
# Driver Code
if __name__ == '__main__':
    L = 2; R = 7;
    countEvenOdd(L, R);
 
# This code is contributed by shikhasingrajput

// C# program for the above approach
using System;
class GFG
{
     
    // Print count of even and odd numbers
    // of XOR value from L to R
    static void countEvenOdd(int L, int R)
    {
       
        // Store the number of elements
        // between L and R
        int range = R - L + 1;
       
        // Count of even XOR values
        int even = (range / 4) * 2;
       
        // If L is odd and range % 4 = 3
        if ((L & 1) != 0 && (range % 4 == 3))
        {
       
            // Increment even by 1
            even++;
        }
       
        // If L is even and range % 4 !=0
        else if ((L & 1) == 0 && (range % 4 != 0))
        {
       
            // Increment even by 1
            even++;
        }
       
        // Print the answer
        Console.Write("Even = " + even +
                      ", Odd = " + (range - even));
    }
 
  // Driver code
  static void Main()
  {
    int L = 2, R = 7;
    countEvenOdd(L, R);
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
 
// Javascript program for the above approach
 
// Print count of even and odd numbers
// of XOR value from L to R
function countEvenOdd(L, R)
{
    // Store the number of elements
    // between L and R
    let range = R - L + 1;
 
    // Count of even XOR values
    let even = parseInt(range / 4) * 2;
 
    // If L is odd and range % 4 = 3
    if ((L & 1) && (range % 4 == 3)) {
 
        // Increment even by 1
        even++;
    }
 
    // If L is even and range % 4 !=0
    else if (!(L & 1) && (range % 4)) {
 
        // Increment even by 1
        even++;
    }
 
    // Print the answer
    document.write("Even = " + even
         + ", Odd = " + (range - even));
}
 
// Driver Code
let L = 2, R = 7;
countEvenOdd(L, R);
 
</script>

Even = 3, Odd = 3

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