Dado un rango [L, R], necesitamos encontrar dos enteros en este rango de modo que su XOR sea el máximo entre todas las opciones posibles de dos enteros. Más formalmente,
dado [L, R], encuentre max (A ^ B) donde L <= A, B
Ejemplos:
Input : L = 8
R = 20
Output : 31
31 is XOR of 15 and 16.
Input : L = 1
R = 3
Output : 3
Una solución simple es generar todos los pares, encontrar sus valores XOR y finalmente devolver el valor XOR máximo.
Una solución eficiente es considerar el patrón de valores binarios de L a R. Podemos ver que el primer bit de L a R cambia de 0 a 1 o permanece en 1, es decir, si tomamos el XOR de dos números cualquiera para obtener el valor máximo de su primer se arreglará el bit, que será el mismo que el primer bit de XOR de L y R.
Después de observar la técnica para obtener el primer bit, podemos ver que si XOR L y R, el bit más significativo de este XOR nos dirá el valor máximo que podemos lograr, es decir, si XOR de L y R es 1xxx donde x puede ser 0 o 1, entonces el valor máximo de XOR que podemos obtener es 1111 porque de L a R tenemos todas las combinaciones posibles de xxx y siempre es posible elegir estos bits de tal manera de dos números que su XOR se convierta en 1. Se explica a continuación con algunos ejemplos,
Examples 1: L = 8 R = 20 L ^ R = (01000) ^ (10100) = (11100) Now as L ^ R is of form (1xxxx) we can get maximum XOR as (11111) by choosing A and B as 15 and 16 (01111 and 10000) Examples 2: L = 16 R = 20 L ^ R = (10000) ^ (10100) = (00100) Now as L ^ R is of form (1xx) we can get maximum xor as (111) by choosing A and B as 19 and 20 (10011 and 10100)
Entonces, la solución de este problema depende únicamente del valor de (L ^ R). Primero calcularemos el valor L^R y luego, a partir de la parte más significativa de este valor, sumaremos todos los 1 para obtener el resultado final.
C++
// C/C++ program to get maximum xor value
// of two numbers in a range
#include <bits/stdc++.h>
using namespace std;
// method to get maximum xor value in range [L, R]
int maxXORInRange(int L, int R)
{
// get xor of limits
int LXR = L ^ R;
// loop to get msb position of L^R
int msbPos = 0;
while (LXR)
{
msbPos++;
LXR >>= 1;
}
// Simply return the required maximum value.
return (pow(2, msbPos)-1);
}
// Driver code to test above methods
int main()
{
int L = 8;
int R = 20;
cout << maxXORInRange(L, R) << endl;
return 0;
}
Java
// Java program to get maximum xor value
// of two numbers in a range
class Xor
{
// method to get maximum xor value in range [L, R]
static int maxXORInRange(int L, int R)
{
// get xor of limits
int LXR = L ^ R;
// loop to get msb position of L^R
int msbPos = 0;
while (LXR > 0)
{
msbPos++;
LXR >>= 1;
}
// construct result by adding 1,
// msbPos times
int maxXOR = 0;
int two = 1;
while (msbPos-- >0)
{
maxXOR += two;
two <<= 1;
}
return maxXOR;
}
// main function
public static void main (String[] args)
{
int L = 8;
int R = 20;
System.out.println(maxXORInRange(L, R));
}
}
Python3
# Python3 program to get maximum xor # value of two numbers in a range # Method to get maximum xor # value in range [L, R] def maxXORInRange(L, R): # get xor of limits LXR = L ^ R # loop to get msb position of L^R msbPos = 0 while(LXR): msbPos += 1 LXR >>= 1 # construct result by adding 1, # msbPos times maxXOR, two = 0, 1 while (msbPos): maxXOR += two two <<= 1 msbPos -= 1 return maxXOR # Driver code L, R = 8, 20 print(maxXORInRange(L, R)) # This code is contributed by Anant Agarwal.
C#
// C# program to get maximum xor
// value of two numbers in a range
using System;
class Xor
{
// method to get maximum xor
// value in range [L, R]
static int maxXORInRange(int L, int R)
{
// get xor of limits
int LXR = L ^ R;
// loop to get msb position of L^R
int msbPos = 0;
while (LXR > 0)
{
msbPos++;
LXR >>= 1;
}
// construct result by
// adding 1, msbPos times
int maxXOR = 0;
int two = 1;
while (msbPos-- >0)
{
maxXOR += two;
two <<= 1;
}
return maxXOR;
}
// Driver code
public static void Main()
{
int L = 8;
int R = 20;
Console.WriteLine(maxXORInRange(L, R));
}
}
// This code is contributed by Anant Agarwal.
PHP
<?php
// PHP program to get maximum
// xor value of two numbers
// in a range
// method to get maximum xor
// value in range [L, R]
function maxXORInRange($L, $R)
{
// get xor of limits
$LXR = $L ^ $R;
// loop to get msb
// position of L^R
$msbPos = 0;
while ($LXR)
{
$msbPos++;
$LXR >>= 1;
}
// construct result by
// adding 1, msbPos times
$maxXOR = 0;
$two = 1;
while ($msbPos--)
{
$maxXOR += $two;
$two <<= 1;
}
return $maxXOR;
}
// Driver Code
$L = 8;
$R = 20;
echo maxXORInRange($L, $R), "\n";
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to get maximum xor
// value of two numbers in a range
// method to get maximum xor
// value in range [L, R]
function maxXORInRange(L, R)
{
// get xor of limits
let LXR = L ^ R;
// loop to get msb position of L^R
let msbPos = 0;
while (LXR > 0)
{
msbPos++;
LXR >>= 1;
}
// construct result by
// adding 1, msbPos times
let maxXOR = 0;
let two = 1;
while (msbPos-- > 0)
{
maxXOR += two;
two <<= 1;
}
return maxXOR;
}
let L = 8;
let R = 20;
document.write(maxXORInRange(L, R));
</script>
Producción :
31
Complejidad del tiempo: O(log(R))
Espacio Auxiliar: O(1)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA