Dados los números enteros positivos N, L y R, tenemos que encontrar el valor máximo de N ⊕ X, donde X ∈ [L, R].
Ejemplos:
Entrada: N = 7
L = 2
R = 23
Salida: 23
Explicación: Cuando X = 16, obtenemos 7 ⊕ 16 = 23 que es el valor máximo para todo X ∈ [2, 23].
Entrada: N = 10
L = 5
R = 12
Salida: 15
Explicación: Cuando X = 5, obtenemos 10 ⊕ 5 = 15 que es el valor máximo para todo X ∈ [5, 12].
Enfoque de fuerza bruta : podemos resolver este problema utilizando el enfoque de fuerza bruta al recorrer todos los enteros en el rango [L, R] y tomar su XOR con N mientras se mantiene un registro del resultado máximo encontrado hasta el momento. La complejidad de este algoritmo será O(R – L), y no es factible cuando las variables de entrada se acercan a valores altos como 10 9 .
Enfoque eficiente : dado que el XOR de dos bits es 1 si y solo si son complementarios entre sí, necesitamos que X tenga bits complementarios al de N para tener el valor máximo. Iteramos desde el bit más grande (log 2 (R) th Bit) hasta el más bajo (0 th Bit). Pueden darse los siguientes dos casos para cada bit:
- Si el bit no está establecido, es decir, 0, intentaremos establecerlo en X. Si establecer este bit en 1 da como resultado que X supere a R, entonces no lo estableceremos.
- Si el bit está activado, es decir, 1, intentaremos desactivarlo en X. Si el valor actual de X ya es mayor o igual que L, podemos desactivar el bit con seguridad. En el otro caso, comprobaremos si configurar todos los siguientes bits es suficiente para mantener X >= L. De lo contrario, debemos configurar el bit actual. Observe que establecer todos los bits siguientes equivale a sumar (1 << b ) – 1, donde b es el bit actual.
La complejidad temporal de este enfoque es O(log 2 (R)).
C++
// CPP program to find the x in range [l, r]
// such that x ^ n is maximum.
#include <cmath>
#include <iostream>
using namespace std;
// Function to calculate the maximum value of
// N ^ X, where X is in the range [L, R]
int maximumXOR(int n, int l, int r)
{
int x = 0;
for (int i = log2(r); i >= 0; --i)
{
if (n & (1 << i)) // Set bit
{
if (x + (1 << i) - 1 < l)
x ^= (1 << i);
}
else // Unset bit
{
if ((x ^ (1 << i)) <= r)
x ^= (1 << i);
}
}
return n ^ x;
}
// Driver Code
int main()
{
int n = 7, l = 2, r = 23;
cout << "The output is " << maximumXOR(n, l, r);
return 0;
}
Java
// Java program to find the x in range [l, r]
// such that x ^ n is maximum.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
// Function to calculate the maximum value of
// N ^ X, where X is in the range [L, R]
static int maximumXOR(int n, int l, int r)
{
int x = 0;
for (int i = (int)(Math.log(r)/Math.log(2)); i >= 0; --i)
{
if ((n & (1 << i))>0) // Set bit
{
if (x + (1 << i) - 1 < l)
x ^= (1 << i);
}
else // Unset bit
{
if ((x ^ (1 << i)) <= r)
x ^= (1 << i);
}
}
return n ^ x;
}
// Driver function
public static void main(String args[])
{
int n = 7, l = 2, r = 23;
System.out.println( "The output is " + maximumXOR(n, l, r));
}
}
// This code is Contributed by tufan_gupta2000
Python3
# Python program to find the
# x in range [l, r] such that
# x ^ n is maximum.
import math
# Function to calculate the
# maximum value of N ^ X,
# where X is in the range [L, R]
def maximumXOR(n, l, r):
x = 0
for i in range(int(math.log2(r)), -1, -1):
if (n & (1 << i)): # Set bit
if (x + (1 << i) - 1 < l):
x ^= (1 << i)
else: # Unset bit
if (x ^ (1 << i)) <= r:
x ^= (1 << i)
return n ^ x
# Driver code
n = 7
l = 2
r = 23
print("The output is",
maximumXOR(n, l, r))
# This code was contributed
# by VishalBachchas
C#
// C# program to find the x in range
// [l, r] such that x ^ n is maximum.
using System;
class GFG
{
// Function to calculate the
// maximum value of N ^ X,
// where X is in the range [L, R]
public static int maximumXOR(int n,
int l, int r)
{
int x = 0;
for (int i = (int)(Math.Log(r) /
Math.Log(2)); i >= 0; --i)
{
if ((n & (1 << i)) > 0) // Set bit
{
if (x + (1 << i) - 1 < l)
{
x ^= (1 << i);
}
}
else // Unset bit
{
if ((x ^ (1 << i)) <= r)
{
x ^= (1 << i);
}
}
}
return n ^ x;
}
// Driver Code
public static void Main(string[] args)
{
int n = 7, l = 2, r = 23;
Console.WriteLine("The output is " +
maximumXOR(n, l, r));
}
}
// This code is contributed
// by Shrikant13
PHP
<?php
// PHP program to find the x in range
// [l, r] such that x ^ n is maximum.
// Function to calculate the maximum
// value of N ^ X, where X is in the
// range [L, R]
function maximumXOR($n, $l, $r)
{
$x = 0;
for ($i = log($r, 2); $i >= 0; --$i)
{
if ($n & (1 << $i))
{
// Set bit
if ($x + (1 << $i) - 1 < $l)
$x ^= (1 << $i);
}
else
{
// Unset bit
if (($x ^ (1 << $i)) <= $r)
$x ^= (1 << $i);
}
}
return $n ^ $x;
}
// Driver Code
$n = 7;
$l = 2;
$r = 23;
echo "The output is " ,
maximumXOR($n, $l, $r);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find
// the x in range [l, r]
// such that x ^ n is maximum.
// Function to calculate the maximum value of
// N ^ X, where X is in the range [L, R]
function maximumXOR(n, l, r)
{
let x = 0;
for (let i =
parseInt(Math.log(r) / Math.log(2)); i >= 0; --i)
{
if (n & (1 << i)) // Set bit
{
if (x + (1 << i) - 1 < l)
x ^= (1 << i);
}
else // Unset bit
{
if ((x ^ (1 << i)) <= r)
x ^= (1 << i);
}
}
return n ^ x;
}
// Driver Code
let n = 7, l = 2, r = 23;
document.write("The output is " + maximumXOR(n, l, r));
</script>
The output is 23
Complejidad temporal: O(log 2 r)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por vaibhav29498 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA