Dado un rango [L, R] , la tarea es encontrar un par (X, Y) tal que L ≤ X, Y ≤ R y (X | Y) sea el máximo entre todos los pares posibles y luego imprimir el OR bit a bit del par encontrado.
Ejemplos:
Entrada: L = 4, R = 5
Salida: 5
El único par es (4, 5) y (4 | 5) = 5.
Entrada: L = 14, R = 2500
Salida: 4095
Enfoque ingenuo: iterar de L a R y verificar el OR bit a bit para cada par posible e imprimir el valor máximo al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <climits>
#include <iostream>
using namespace std;
// Function to return the maximum bitwise OR
// possible among all the possible pairs
int maxOR(int L, int R)
{
int maximum = INT_MIN;
// Check for every possible pair
for (int i = L; i < R; i++)
for (int j = i + 1; j <= R; j++)
// Maximum among all (i, j) pairs
maximum = max(maximum, (i | j));
return maximum;
}
// Driver code
int main()
{
int L = 4, R = 5;
cout << maxOR(L, R);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the maximum bitwise OR
// possible among all the possible pairs
static int maxOR(int L, int R)
{
int maximum = Integer.MIN_VALUE;
// Check for every possible pair
for (int i = L; i < R; i++)
for (int j = i + 1; j <= R; j++)
// Maximum among all (i, j) pairs
maximum = Math.max(maximum, (i | j));
return maximum;
}
// Driver code
public static void main(String []args)
{
int L = 4, R = 5;
System.out.println(maxOR(L, R));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return the maximum bitwise OR # possible among all the possible pairs def maxOR(L, R): maximum = -10**9 # Check for every possible pair for i in range(L, R): for j in range(i + 1, R + 1): # Maximum among all (i, j) pairs maximum = max(maximum, (i | j)) return maximum # Driver code L = 4 R = 5 print(maxOR(L, R)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the maximum bitwise OR
// possible among all the possible pairs
static int maxOR(int L, int R)
{
int maximum = int.MinValue;
// Check for every possible pair
for (int i = L; i < R; i++)
for (int j = i + 1; j <= R; j++)
// Maximum among all (i, j) pairs
maximum = Math.Max(maximum, (i | j));
return maximum;
}
// Driver code
public static void Main(String []args)
{
int L = 4, R = 5;
Console.WriteLine(maxOR(L, R));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the maximum bitwise OR
// possible among all the possible pairs
function maxOR(L, R)
{
let maximum = Number.MIN_VALUE;
// Check for every possible pair
for (let i = L; i < R; i++)
for (let j = i + 1; j <= R; j++)
// Maximum among all (i, j) pairs
maximum = Math.max(maximum, (i | j));
return maximum;
}
// Driver code
let L = 4, R = 5;
document.write(maxOR(L, R));
// This code is contributed by shivanisinghss2110
</script>
5
Complejidad temporal: O(n 2 )
Espacio auxiliar: O(1)
Enfoque eficiente: la operación OR establece el i -ésimo bit si cualquiera de los operandos tiene el i -ésimo bit establecido. Nuestro objetivo es maximizar el número de bits establecidos.
Ahora la tarea es encontrar el bit B más significativo donde L y R difieren. El bit B se establecerá en R y no en L. El OR máximo que se puede generar tendrá todos los bits significativos para el bit B igual que L y R y todos los bits menos significativos que Bse establecerán ya que serán inclusivos en el rango. B th bit será 1 en el OR como 1 | 0 será 1.
Ahora, considere las representaciones binarias de L y R , desde el bit más significativo (MSB) hasta el bit menos significativo (LSB). Suponga que los primeros x bits son los mismos para L y R. Entonces, todos los A y B posibles tienen los primeros x bits iguales a L y R , ya que incluso si cambia un solo bit entre estos x bits, el valor se moverá fuera del rango [L, R], lo cual no está permitido.
A continuación, se establecerán todos los bits menos significativos que el bit de diferencia B , incluido B .
Considere el siguiente ejemplo,
L = 001100010
R = 001100110 Los
primeros seis bits son iguales para L y R , por lo que todos los números N, tales que L≤ N < R se mantienen, tendrán sus primeros seis bits iguales a L (o R ) y también O de cualquiera de los dos números en el rango tendrá los mismos primeros seis bits.
Ahora, ignorando la primera xbits, encontramos una discrepancia en el bit. En este punto, A puede construirse de manera que el bit no coincidente no se establezca para A y se establezcan todos los bits menos significativos que el bit actual. De manera similar, B puede construirse de manera que el bit de desajuste se establezca para B y todos los bits subsiguientes no se establezcan en B.
Su OR tendrá todos los bits, incluido el bit de desajuste establecido.
Aplicando esta lógica a nuestro ejemplo, tenemos A = 001100011 y B = 001100100 y su OR es 001100111, que es el máximo posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
const int MAX = 64;
// Function to return the maximum bitwise OR
// possible among all the possible pairs
int maxOR(int L, int R)
{
// If there is only a single value
// in the range [L, R]
if (L == R) {
return L;
}
int ans = 0;
// Loop through each bit from MSB to LSB
for (int i = MAX - 1; i >= 0; i--) {
int p, lbit, rbit;
p = 1 << i;
lbit = (L >> i) & 1; // bit of left limit
rbit = (R >> i) & 1; // bit of right limit
// MSBs where the bits differ,
// all bits from that bit are set
if ((rbit == 1) && (lbit == 0)) {
ans += (p << 1) - 1;
break;
}
// If MSBs are same, then ans
// bit is same as that of
// bit of right or left limit
if (rbit == 1) {
ans += p;
}
}
return ans;
}
// Driver code
int main()
{
int L = 4, R = 5;
cout << maxOR(L, R);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MAX = 64;
// Function to return the maximum bitwise OR
// possible among all the possible pairs
static int maxOR(int L, int R)
{
// If there is only a single value
// in the range [L, R]
if (L == R)
{
return L;
}
int ans = 0;
// Loop through each bit from MSB to LSB
for (int i = MAX - 1; i >= 0; i--)
{
int p, lbit, rbit;
p = 1 << i;
lbit = (L >> i) & 1; // bit of left limit
rbit = (R >> i) & 1; // bit of right limit
// MSBs where the bits differ,
// all bits from that bit are set
if ((rbit == 1) && (lbit == 0))
{
ans += (p << 1) - 1;
break;
}
// If MSBs are same, then ans
// bit is same as that of
// bit of right or left limit
if (rbit == 1)
{
ans += p;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int L = 4, R = 5;
System.out.println(maxOR(L, R));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach MAX = 64; # Function to return the maximum bitwise OR # possible among all the possible pairs def maxOR(L, R) : # If there is only a single value # in the range [L, R] if (L == R) : return L; ans = 0; # Loop through each bit from MSB to LSB for i in range(MAX - 1, -1, -1) : p = 1 << i; lbit = (L >> i) & 1; # bit of left limit rbit = (R >> i) & 1; # bit of right limit # MSBs where the bits differ, # all bits from that bit are set if ((rbit == 1) and (lbit == 0)) : ans += (p << 1) - 1; break; # If MSBs are same, then ans # bit is same as that of # bit of right or left limit if (rbit == 1) : ans += p; return ans; # Driver code if __name__ == "__main__" : L = 4; R = 5; print(maxOR(L, R)); # This code is contributed by kanugargng
C#
// C# implementation of the above approach
using System;
class GFG
{
static int MAX = 64;
// Function to return the maximum bitwise OR
// possible among all the possible pairs
static int maxOR(int L, int R)
{
// If there is only a single value
// in the range [L, R]
if (L == R)
{
return L;
}
int ans = 0;
// Loop through each bit from MSB to LSB
for (int i = MAX - 1; i >= 0; i--)
{
int p, lbit, rbit;
p = 1 << i;
lbit = (L >> i) & 1; // bit of left limit
rbit = (R >> i) & 1; // bit of right limit
// MSBs where the bits differ,
// all bits from that bit are set
if ((rbit == 1) && (lbit == 0))
{
ans += (p << 1) - 1;
break;
}
// If MSBs are same, then ans
// bit is same as that of
// bit of right or left limit
if (rbit == 1)
{
ans += p;
}
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int L = 4, R = 5;
Console.WriteLine(maxOR(L, R));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
let MAX = 64;
// Function to return the maximum bitwise OR
// possible among all the possible pairs
function maxOR(L,R)
{
// If there is only a single value
// in the range [L, R]
if (L == R)
{
return L;
}
let ans = 0;
// Loop through each bit from MSB to LSB
for (let i = MAX - 1; i >= 0; i--)
{
let p, lbit, rbit;
p = 1 << i;
lbit = (L >> i) & 1; // bit of left limit
rbit = (R >> i) & 1; // bit of right limit
// MSBs where the bits differ,
// all bits from that bit are set
if ((rbit == 1) && (lbit == 0))
{
ans += (p << 1) - 1;
break;
}
// If MSBs are same, then ans
// bit is same as that of
// bit of right or left limit
if (rbit == 1)
{
ans += p;
}
}
return ans;
}
// Driver code
let L = 4, R = 5;
document.write(maxOR(L, R));
// This code is contributed by unknown2108
</script>
5
Complejidad temporal: O(log 2 (R)), donde R es el límite superior del rango.
Espacio Auxiliar: O(1)