Dados dos enteros L y R , la tarea es encontrar el XOR de los elementos del rango [L, R] .
Ejemplos:
Entrada: L = 4, R = 8
Salida: 8
4 ^ 5 ^ 6 ^ 7 ^ 8 = 8Entrada: L = 3, R = 7
Salida: 3
Enfoque ingenuo: inicialice la respuesta como cero, recorra todos los números de L a R y realice XOR de los números uno por uno con la respuesta. Esto tomaría tiempo O(N) .
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the XOR of elements
// from the range [l, r]
int findXOR(int l, int r)
{
int ans = 0;
for (int i = l; i <= r; i++) {
ans = ans ^ i;
}
return ans;
}
// Driver code
int main()
{
int l = 4, r = 8;
cout << findXOR(l, r);
return 0;
}
// this code is contributed by devendra solunke
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Function to return the XOR of elements
// from the range [l, r]
public static int findXOR(int l, int r)
{
int ans = 0;
for (int i = l; i <= r; i++) {
ans = ans ^ i;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int l = 4;
int r = 8;
System.out.println(findXOR(l, r));
}
}
// this code is contributed by devendra solunke
C#
// c# implementation of find xor between given range
using System;
public class GFG {
// Function to return the XOR of elements
// from the range [l, r]
static int findXOR(int l, int r)
{
int ans = 0;
for (int i = l; i <= r; i++) {
ans = ans ^ i;
}
return ans;
}
// Driver code
static void Main(String[] args)
{
int l = 4;
int r = 8;
Console.WriteLine(findXOR(l, r));
}
}
// this code is contributed by devendra saunke
Javascript
// Javascript code to find xor of given range
<script>
var l = 4;
var r = 8;
var ans = 0;
var(int i = l; i <= r; i++)
{
ans = ans ^ i;
}
document.write(ans);
</script>
// this code is contributed by devendra solunke
8
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: siguiendo el enfoque discutido aquí , podemos encontrar el XOR de elementos del rango [1, N] en tiempo O(1) .
Usando este enfoque, tenemos que encontrar xor de elementos del rango [1, L – 1] y del rango [1, R] y luego xor las respuestas respectivas nuevamente para obtener xor de los elementos del rango [L, R] . Esto se debe a que cada elemento del rango [1, L – 1] obtendrá XOR dos veces en el resultado, lo que dará como resultado un 0 que, cuando se aplica XOR con los elementos del rango [L, R] , dará el resultado.
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 XOR of elements
// from the range [1, n]
int findXOR(int n)
{
int mod = n % 4;
// If n is a multiple of 4
if (mod == 0)
return n;
// If n % 4 gives remainder 1
else if (mod == 1)
return 1;
// If n % 4 gives remainder 2
else if (mod == 2)
return n + 1;
// If n % 4 gives remainder 3
else if (mod == 3)
return 0;
}
// Function to return the XOR of elements
// from the range [l, r]
int findXOR(int l, int r)
{
return (findXOR(l - 1) ^ findXOR(r));
}
// Driver code
int main()
{
int l = 4, r = 8;
cout << findXOR(l, r);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the XOR of elements
// from the range [1, n]
static int findXOR(int n)
{
int mod = n % 4;
// If n is a multiple of 4
if (mod == 0)
return n;
// If n % 4 gives remainder 1
else if (mod == 1)
return 1;
// If n % 4 gives remainder 2
else if (mod == 2)
return n + 1;
// If n % 4 gives remainder 3
else if (mod == 3)
return 0;
return 0;
}
// Function to return the XOR of elements
// from the range [l, r]
static int findXOR(int l, int r)
{
return (findXOR(l - 1) ^ findXOR(r));
}
// Driver code
public static void main(String[] args)
{
int l = 4, r = 8;
System.out.println(findXOR(l, r));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of the approach from operator import xor # Function to return the XOR of elements # from the range [1, n] def findXOR(n): mod = n % 4; # If n is a multiple of 4 if (mod == 0): return n; # If n % 4 gives remainder 1 elif (mod == 1): return 1; # If n % 4 gives remainder 2 elif (mod == 2): return n + 1; # If n % 4 gives remainder 3 elif (mod == 3): return 0; # Function to return the XOR of elements # from the range [l, r] def findXORFun(l, r): return (xor(findXOR(l - 1) , findXOR(r))); # Driver code l = 4; r = 8; print(findXORFun(l, r)); # This code is contributed by PrinciRaj1992
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the XOR of elements
// from the range [1, n]
static int findXOR(int n)
{
int mod = n % 4;
// If n is a multiple of 4
if (mod == 0)
return n;
// If n % 4 gives remainder 1
else if (mod == 1)
return 1;
// If n % 4 gives remainder 2
else if (mod == 2)
return n + 1;
// If n % 4 gives remainder 3
else if (mod == 3)
return 0;
return 0;
}
// Function to return the XOR of elements
// from the range [l, r]
static int findXOR(int l, int r)
{
return (findXOR(l - 1) ^ findXOR(r));
}
// Driver code
public static void Main()
{
int l = 4, r = 8;
Console.WriteLine(findXOR(l, r));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Function to return the XOR of elements
// from the range [1, n]
function findxOR(n)
{
let mod = n % 4;
// If n is a multiple of 4
if (mod == 0)
return n;
// If n % 4 gives remainder 1
else if (mod == 1)
return 1;
// If n % 4 gives remainder 2
else if (mod == 2)
return n + 1;
// If n % 4 gives remainder 3
else if (mod == 3)
return 0;
}
// Function to return the XOR of elements
// from the range [l, r]
function findXOR(l, r)
{
return (findxOR(l - 1) ^ findxOR(r));
}
let l = 4, r = 8;
document.write(findXOR(l, r));
</script>
8
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por NikhilRathor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA