Dados dos números enteros L y R , la tarea es calcular Bitwise XOR de todos los números pares en el rango [L, R] .
Ejemplos:
Ejemplo:
Entrada: L = 10, R = 20
Salida: 30
Explicación:
Bitwise XOR = 10 ^ 12 ^ 14 ^ 16 ^ 18 ^ 20 = 30
Por lo tanto, la salida requerida es 30.Ejemplo:
Entrada: L = 15, R = 23
Salida: 0
Explicación:
Bitwise XOR = 16 ^ 18 ^ 20 ^ 22 = 0
Por lo tanto, la salida requerida es 0.
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar todos los números pares en el rango [L, R] e imprimir el XOR bit a bit de todos los números pares.
Complejidad temporal: O(R – L)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
Si N es un número par:
2 ^ 4 … ^ (N) = 2 * (1 ^ 2 ^ … ^ (N / 2))Si N es un número impar:
2 ^ 4 … ^ (N) = 2 * (1 ^ 2 ^ … ^ ((N – 1) / 2))
Siga los pasos a continuación para resolver el problema:
- Encuentre el XOR bit a bit de todos los números del rango [1, (R) / 2] y guárdelo en una variable, digamos xor_r .
- Encuentre el XOR bit a bit de todos los números del rango [1, (L – 1) / 2] y guárdelo en una variable, digamos xor_l.
- Finalmente, imprime el valor de xor_r ^ xor_l .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate XOR of
// numbers in the range [1, n]
int bitwiseXorRange(int n)
{
// If n is divisible by 4
if (n % 4 == 0)
return n;
// If n mod 4 is equal to 1
if (n % 4 == 1)
return 1;
// If n mod 4 is equal to 2
if (n % 4 == 2)
return n + 1;
return 0;
}
// Function to find XOR of even
// numbers in the range [l, r]
int evenXorRange(int l, int r)
{
// Stores XOR of even numbers
// in the range [1, l - 1]
int xor_l;
// Stores XOR of even numbers
// in the range [1, r]
int xor_r;
// Update xor_r
xor_r
= 2 * bitwiseXorRange(r / 2);
// Update xor_l
xor_l
= 2 * bitwiseXorRange((l - 1) / 2);
return xor_l ^ xor_r;
}
// Driver Code
int main()
{
int l = 10;
int r = 20;
cout << evenXorRange(l, r);
return 0;
}
Java
// Java Implementation of the above approach
class GFG
{
// Function to calculate XOR of
// numbers in the range [1, n]
static int bitwiseXorRange(int n)
{
// If n is divisible by 4
if (n % 4 == 0)
return n;
// If n mod 4 is equal to 1
if (n % 4 == 1)
return 1;
// If n mod 4 is equal to 2
if (n % 4 == 2)
return n + 1;
return 0;
}
// Function to find XOR of even
// numbers in the range [l, r]
static int evenXorRange(int l, int r)
{
// Stores XOR of even numbers
// in the range [1, l - 1]
int xor_l;
// Stores XOR of even numbers
// in the range [1, r]
int xor_r;
// Update xor_r
xor_r
= 2 * bitwiseXorRange(r / 2);
// Update xor_l
xor_l
= 2 * bitwiseXorRange((l - 1) / 2);
return xor_l ^ xor_r;
}
// Driver Code
public static void main (String[] args)
{
int l = 10;
int r = 20;
System.out.print(evenXorRange(l, r));
}
}
// This code is contributed by AnkThon
Python3
# Python3 implementation of the above approach # Function to calculate XOR of # numbers in the range [1, n] def bitwiseXorRange(n): # If n is divisible by 4 if (n % 4 == 0): return n # If n mod 4 is equal to 1 if (n % 4 == 1): return 1 # If n mod 4 is equal to 2 if (n % 4 == 2): return n + 1 return 0 # Function to find XOR of even # numbers in the range [l, r] def evenXorRange(l, r): # Stores XOR of even numbers # in the range [1, l - 1] #xor_l # Stores XOR of even numbers # in the range [1, r] #xor_r # Update xor_r xor_r = 2 * bitwiseXorRange(r // 2) # Update xor_l xor_l = 2 * bitwiseXorRange((l - 1) // 2) return xor_l ^ xor_r # Driver Code if __name__ == '__main__': l = 10 r = 20 print(evenXorRange(l, r)) # This code is contributed by mohit kumar 29
C#
// C# Implementation of the above approach
using System;
class GFG {
// Function to calculate XOR of
// numbers in the range [1, n]
static int bitwiseXorRange(int n)
{
// If n is divisible by 4
if (n % 4 == 0)
return n;
// If n mod 4 is equal to 1
if (n % 4 == 1)
return 1;
// If n mod 4 is equal to 2
if (n % 4 == 2)
return n + 1;
return 0;
}
// Function to find XOR of even
// numbers in the range [l, r]
static int evenXorRange(int l, int r)
{
// Stores XOR of even numbers
// in the range [1, l - 1]
int xor_l;
// Stores XOR of even numbers
// in the range [1, r]
int xor_r;
// Update xor_r
xor_r
= 2 * bitwiseXorRange(r / 2);
// Update xor_l
xor_l
= 2 * bitwiseXorRange((l - 1) / 2);
return xor_l ^ xor_r;
}
// Driver code
static void Main()
{
int l = 10;
int r = 20;
Console.Write(evenXorRange(l, r));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript Implementation of the above approach
// Function to calculate XOR of
// numbers in the range [1, n]
function bitwiseXorRange(n)
{
// If n is divisible by 4
if (n % 4 == 0)
return n;
// If n mod 4 is equal to 1
if (n % 4 == 1)
return 1;
// If n mod 4 is equal to 2
if (n % 4 == 2)
return n + 1;
return 0;
}
// Function to find XOR of even
// numbers in the range [l, r]
function evenXorRange(l, r)
{
// Stores XOR of even numbers
// in the range [1, l - 1]
let xor_l;
// Stores XOR of even numbers
// in the range [1, r]
let xor_r;
// Update xor_r
xor_r
= 2 * bitwiseXorRange(Math.floor(r / 2));
// Update xor_l
xor_l
= 2 * bitwiseXorRange(Math.floor((l - 1) / 2));
return xor_l ^ xor_r;
}
// Driver Code
let l = 10;
let r = 20;
document.write(evenXorRange(l, r));
// This code is contributed by Surbhi Tyagi.
</script>
30
Complejidad Temporal: 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