Dado un rango [L, R] , la tarea es encontrar el XOR de todos los enteros en el rango dado, es decir, (L) ^ (L + 1) ^ (L + 2) ^ … ^ (R)
Ejemplos:
Entrada: L = 1, R = 4
Salida: 4
1 ^ 2 ^ 3 ^ 4 = 4
Entrada: L = 3, R = 9
Salida: 2
Una solución simple es encontrar XOR de todos los números iterativamente de L a R. Esto tomará un tiempo lineal.
Una mejor solución es encontrar primero el bit más significativo en el entero R. Nuestra respuesta no puede ser un poco más grande que la de ‘R’. Para cada bit ‘i’ entre 0 y MSB inclusive, intentaremos determinar la paridad de conteo de un número de enteros entre L y R inclusive, de modo que se establezca el bit ‘i -ésimo ‘. Si el conteo es impar, también se establecerá el bit ‘i -ésimo ‘ de nuestra respuesta final.
Ahora, la verdadera pregunta es, para el i -ésimo bit, ¿cómo determinamos la paridad de la cuenta?
Para tener una idea, veamos la representación binaria de los primeros 16 enteros.
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
9: 1001
10: 1010
11: 1011
12: 1100
13: 1101
14: 1110 1
5: 1111
Es fácilmente perceptible que el estado del i -ésimo bit cambia después de cada 2i número. Usaremos esta idea para predecir el conteo de un número de enteros con i -ésimo bit establecido en el rango L a R inclusive.
Aquí tenemos dos casos:
- Caso 1(i != 0): Tratamos de determinar si el i -ésimo bit de L está activado o no. Si se establece, tratamos de encontrar la paridad de la cuenta de números entre L y L + 2 i inclusive, de modo que se establezca su i -ésimo bit. Si se establece i -ésimo bit de L y L es impar, entonces este conteo será impar o par.
De manera similar para R, tratamos de determinar la paridad del conteo de un número de elementos entre R – 2 i y R, de modo que se establezca su i -ésimo bit. Si se establece i -ésimo bit de L y L es par, entonces este conteo será impar o par.
Ignoramos todos los demás enteros intermedios porque tendrán un número par de enteros con i -ésimo bit establecido. - Caso 2(i = 0): Aquí tenemos los siguientes casos:
- Si L y R, ambos son impares, la cuenta del número de enteros con el bit 0 th establecido será (R – L)/2 + 1
- En cualquier otro caso, el conteo será piso((R – L + 1)/2) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// most significant bit
int msb(int x)
{
int ret = 0;
while ((x >> (ret + 1)) != 0)
ret++;
return ret;
}
// Function to return the required XOR
int xorRange(int l, int r)
{
// Finding the MSB
int max_bit = msb(r);
// Value of the current bit to be added
int mul = 2;
// To store the final answer
int ans = 0;
// Loop for case 1
for (int i = 1; i <= max_bit; i++) {
// Edge case when both the integers
// lie in the same segment of continuous
// 1s
if ((l / mul) * mul == (r / mul) * mul) {
if (((l & (1 << i)) != 0) && (r - l + 1) % 2 == 1)
ans += mul;
mul *= 2;
continue;
}
// To store whether parity of count is odd
bool odd_c = 0;
if (((l & (1 << i)) != 0) && l % 2 == 1)
odd_c = (odd_c ^ 1);
if (((r & (1 << i)) != 0) && r % 2 == 0)
odd_c = (odd_c ^ 1);
// Updating the answer if parity is odd
if (odd_c)
ans += mul;
// Updating the number to be added
mul *= 2;
}
// Case 2
int zero_bit_cnt = zero_bit_cnt = (r - l + 1) / 2;
if (l % 2 == 1 && r % 2 == 1)
zero_bit_cnt++;
if (zero_bit_cnt % 2 == 1)
ans++;
return ans;
}
// Driver code
int main()
{
int l = 1, r = 4;
// Final answer
cout << xorRange(l, r);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the
// most significant bit
static int msb(int x)
{
int ret = 0;
while ((x >> (ret + 1)) != 0)
ret++;
return ret;
}
// Function to return the required XOR
static int xorRange(int l, int r)
{
// Finding the MSB
int max_bit = msb(r);
// Value of the current bit to be added
int mul = 2;
// To store the final answer
int ans = 0;
// Loop for case 1
for (int i = 1; i <= max_bit; i++)
{
// Edge case when both the integers
// lie in the same segment of continuous
// 1s
if ((l / mul) * mul == (r / mul) * mul)
{
if (((l & (1 << i)) != 0) && (r - l + 1) % 2 == 1)
ans += mul;
mul *= 2;
continue;
}
// To store whether parity of count is odd
int odd_c = 0;
if (((l & (1 << i)) != 0) && l % 2 == 1)
odd_c = (odd_c ^ 1);
if (((r & (1 << i)) != 0) && r % 2 == 0)
odd_c = (odd_c ^ 1);
// Updating the answer if parity is odd
if (odd_c!=0)
ans += mul;
// Updating the number to be added
mul *= 2;
}
// Case 2
int zero_bit_cnt = zero_bit_cnt = (r - l + 1) / 2;
if (l % 2 == 1 && r % 2 == 1)
zero_bit_cnt++;
if (zero_bit_cnt % 2 == 1)
ans++;
return ans;
}
// Driver code
public static void main(String args[])
{
int l = 1, r = 4;
// Final answer
System.out.print(xorRange(l, r));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Function to return the most significant bit def msb(x) : ret = 0 while ((x >> (ret + 1)) != 0) : ret = ret + 1 return ret # Function to return the required XOR def xorRange(l, r) : # Finding the MSB max_bit = msb(r) # Value of the current bit to be added mul = 2 # To store the final answer ans = 0 # Loop for case 1 for i in range (1, max_bit + 1) : # Edge case when both the integers # lie in the same segment of continuous # 1s if ((l // mul) * mul == (r // mul) * mul) : if ((((l & (1 << i)) != 0) and (r - l + 1) % 2 == 1)) : ans = ans + mul mul = mul * 2 continue # To store whether parity of count is odd odd_c = 0 if (((l & (1 << i)) != 0) and l % 2 == 1) : odd_c = (odd_c ^ 1) if (((r & (1 << i)) != 0) and r % 2 == 0) : odd_c = (odd_c ^ 1) # Updating the answer if parity is odd if (odd_c) : ans = ans + mul # Updating the number to be added mul = mul * 2 # Case 2 zero_bit_cnt = (r - l + 1) // 2 if ((l % 2 == 1 ) and (r % 2 == 1)) : zero_bit_cnt = zero_bit_cnt + 1 if (zero_bit_cnt % 2 == 1): ans = ans + 1 return ans # Driver code l = 1 r = 4 # Final answer print(xorRange(l, r)) # This code is contributed by ihritik
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the
// most significant bit
static int msb(int x)
{
int ret = 0;
while ((x >> (ret + 1)) != 0)
ret++;
return ret;
}
// Function to return the required XOR
static int xorRange(int l, int r)
{
// Finding the MSB
int max_bit = msb(r);
// Value of the current bit to be added
int mul = 2;
// To store the final answer
int ans = 0;
// Loop for case 1
for (int i = 1; i <= max_bit; i++)
{
// Edge case when both the integers
// lie in the same segment of continuous
// 1s
if ((l / mul) * mul == (r / mul) * mul)
{
if (((l & (1 << i)) != 0) && (r - l + 1) % 2 == 1)
ans += mul;
mul *= 2;
continue;
}
// To store whether parity of count is odd
int odd_c = 0;
if (((l & (1 << i)) != 0) && l % 2 == 1)
odd_c = (odd_c ^ 1);
if (((r & (1 << i)) != 0) && r % 2 == 0)
odd_c = (odd_c ^ 1);
// Updating the answer if parity is odd
if (odd_c!=0)
ans += mul;
// Updating the number to be added
mul *= 2;
}
// Case 2
int zero_bit_cnt = zero_bit_cnt = (r - l + 1) / 2;
if (l % 2 == 1 && r % 2 == 1)
zero_bit_cnt++;
if (zero_bit_cnt % 2 == 1)
ans++;
return ans;
}
// Driver code
public static void Main(String []args)
{
int l = 1, r = 4;
// Final answer
Console.Write(xorRange(l, r));
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP implementation of the approach
// Function to return the
// most significant bit
function msb($x)
{
$ret = 0;
while (($x >> ($ret + 1)) != 0)
$ret++;
return $ret;
}
// Function to return the required XOR
function xorRange($l, $r)
{
// Finding the MSB
$max_bit = msb($r);
// Value of the current bit to be added
$mul = 2;
// To store the final answer
$ans = 0;
// Loop for case 1
for ($i = 1; $i <= $max_bit; $i++)
{
// Edge case when both the integers
// lie in the same segment of continuous
// 1s
if ((int)(($l / $mul) * $mul) ==
(int)(($r / $mul) * $mul))
{
if ((($l & (1 << $i)) != 0) &&
($r - $l + 1) % 2 == 1)
$ans += $mul;
$mul *= 2;
continue;
}
// To store whether parity of count is odd
$odd_c = 0;
if ((($l & (1 << $i)) != 0) && $l % 2 == 1)
$odd_c = ($odd_c ^ 1);
if ((($r & (1 << $i)) != 0) && $r % 2 == 0)
$odd_c = ($odd_c ^ 1);
// Updating the answer if parity is odd
if ($odd_c)
$ans += $mul;
// Updating the number to be added
$mul *= 2;
}
// Case 2
$zero_bit_cnt = (int)(($r - $l + 1) / 2);
if ($l % 2 == 1 && $r % 2 == 1)
$zero_bit_cnt++;
if ($zero_bit_cnt % 2 == 1)
$ans++;
return $ans;
}
// Driver code
$l = 1;
$r = 4;
// Final answer
echo xorRange($l, $r);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the
// most significant bit
function msb(x)
{
let ret = 0;
while ((x >> (ret + 1)) != 0)
ret++;
return ret;
}
// Function to return the required XOR
function xorRange(l, r)
{
// Finding the MSB
let max_bit = msb(r);
// Value of the current bit to be added
let mul = 2;
// To store the final answer
let ans = 0;
// Loop for case 1
for (let i = 1; i <= max_bit; i++) {
// Edge case when both the integers
// lie in the same segment of continuous
// 1s
if ((parseInt(l / mul) * mul) ==
(parseInt(r / mul) * mul))
{
if (((l & (1 << i)) != 0) &&
(r - l + 1) % 2 == 1)
ans += mul;
mul *= 2;
continue;
}
// To store whether parity of count is odd
let odd_c = 0;
if (((l & (1 << i)) != 0) && l % 2 == 1)
odd_c = (odd_c ^ 1);
if (((r & (1 << i)) != 0) && r % 2 == 0)
odd_c = (odd_c ^ 1);
// Updating the answer if parity is odd
if (odd_c)
ans += mul;
// Updating the number to be added
mul *= 2;
}
// Case 2
let zero_bit_cnt = parseInt((r - l + 1) / 2);
if (l % 2 == 1 && r % 2 == 1)
zero_bit_cnt++;
if (zero_bit_cnt % 2 == 1)
ans++;
return ans;
}
// Driver code
let l = 1, r = 4;
// Final answer
document.write(xorRange(l, r));
</script>
Producción:
4
Complejidad del tiempo: O(log 2 (R))
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.
Enfoque eficiente: Sea F(N) una función que calcula XOR de todos los números naturales menores o iguales que N. Por lo tanto, para el rango (LR), la respuesta será F(R) ^ F(L-1) .
Encontrar el valor de esta función para cualquier número dado es posible en O(1) como se explica en este artículo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the required XOR
long computeXOR(const int n)
{
// Modulus operator are expensive
// on most of the computers.
// n & 3 will be equivalent to n % 4
// n % 4
switch (n & 3) {
// If n is a 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;
}
}
// Driver code
int main()
{
int l = 1, r = 4;
cout << (computeXOR(r) ^ computeXOR(l - 1));
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the required XOR
static long computeXOR(int n)
{
// Modulus operator are expensive
// on most of the computers.
// n & 3 will be equivalent to n % 4
// n % 4
int x = n & 3;
switch (x)
{
// If n is a 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;
}
return 0;
}
// Driver code
public static void main(String args[])
{
int l = 1, r = 4;
System.out.println(computeXOR(r) ^
computeXOR(l - 1));
}
}
// This code is contributed by Ryuga
Python3
# Python3 implementation of the approach
# Function to return the required XOR
def computeXOR(n) :
# Modulus operator are expensive
# on most of the computers.
# n & 3 will be equivalent to n % 4
# n % 4
switch = {
# If n is a multiple of 4
0 : n,
# If n % 4 gives remainder 1
1 : 1,
# If n % 4 gives remainder 2
2: n + 1,
# If n % 4 gives remainder 3
3 : 0,
}
return switch.get( n & 3, "")
# Driver code
l = 1
r = 4
print(computeXOR(r) ^ computeXOR(l - 1))
# This code is contributed by ihritik
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the required XOR
static long computeXOR(int n)
{
// Modulus operator are expensive
// on most of the computers.
// n & 3 will be equivalent to n % 4
// n % 4
int x=n&3;
switch (x)
{
// If n is a 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;
}
return 0;
}
// Driver code
static void Main()
{
int l = 1, r = 4;
Console.WriteLine(computeXOR(r) ^ computeXOR(l - 1));
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the approach
// Function to return the required XOR
function computeXOR($n)
{
// Modulus operator are expensive
// on most of the computers.
// n & 3 will be equivalent to n % 4
// n % 4
$x = $n & 3;
switch ($x)
{
// If n is a 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;
}
return 0;
}
// Driver code
$l = 1; $r = 4;
echo(computeXOR($r) ^ computeXOR($l - 1));
// This code is contributed by Code_Mech
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the required XOR
function computeXOR(n)
{
// Modulus operator are expensive
// on most of the computers.
// n & 3 will be equivalent to n % 4
// n % 4
switch (n & 3) {
// If n is a 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;
}
}
// Driver code
let l = 1, r = 4;
document.write(computeXOR(r) ^ computeXOR(l - 1));
// This code is contributed by subhammahato348.
</script>
Producción:
4
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA