Dado un rango [L, R] , la tarea es encontrar el OR bit a bit máximo de algún par (a, b) del rango dado.
Ejemplos:
Entrada: L = 10, R = 20
Salida: 31
Entrada: L = 56, R = 77
Salida: 127
Enfoque: primero, convierta los números enteros L y R dados en sus representaciones binarias. Ahora, si L tiene menos cantidad de bits que R , entonces presione cero en el lado MSB de L para que la cantidad de bits de L y R sea igual.
Ahora, desde el lado MSB, compare los bits individuales de L y R . Como R es mayor que L , encontraremos el caso cuando el i -ésimo bit de R es 1 y el i -ésimo bit de L es0 _ Entonces, después del i -ésimo bit, haga que todos los bits de L sean 1 . Esto asegura que las modificaciones realizadas en los bits de L no excederán a R , por lo que será solo entre L y R. Y hacer esto también asegura el máximo bit a bit o.
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 maximum bitwise // OR of any pair from the given range long long int max_bitwise_or(long long int L, long long int R) { vector<long long int> v1, v2, v3; long long int z = 0, i, ans = 0, cnt = 1; // Converting L to its binary representation while (L > 0) { v1.push_back(L % 2); L = L / 2; } // Converting R to its binary representation while (R > 0) { v2.push_back(R % 2); R = R / 2; } // In order to make the number // of bits of L and R same while (v1.size() != v2.size()) { // Push 0 to the MSB v1.push_back(0); } for (i = v2.size() - 1; i >= 0; i--) { // When ith bit of R is 1 // and ith bit of L is 0 if (v2[i] == 1 && v1[i] == 0 && z == 0) { z = 1; continue; } // From MSB side set all bits of L to be 1 if (z == 1) { // From (i+1)th bit, all bits // of L changed to be 1 v1[i] = 1; } } for (i = 0; i < v2.size(); i++) { v3.push_back(v2[i] | v1[i]); } for (i = 0; i < v2.size(); i++) { if (v3[i] == 1) { ans += cnt; } cnt *= 2; } return ans; } // Driver code int main() { long long int L = 10, R = 20; cout << max_bitwise_or(L, R); return 0; }
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to return the maximum bitwise // OR of any pair from the given range static int max_bitwise_or(int L, int R) { Vector<Integer> v1 = new Vector<Integer>(), v2 = new Vector<Integer>(), v3 = new Vector<Integer>(); int z = 0, i, ans = 0, cnt = 1; // Converting L to its binary representation while (L > 0) { v1.add(L % 2); L = L / 2; } // Converting R to its binary representation while (R > 0) { v2.add(R % 2); R = R / 2; } // In order to make the number // of bits of L and R same while (v1.size() != v2.size()) { // Push 0 to the MSB v1.add(0); } for (i = v2.size() - 1; i >= 0; i--) { // When ith bit of R is 1 // and ith bit of L is 0 if (v2.get(i) == 1 && v1.get(i) == 0 && z == 0) { z = 1; continue; } // From MSB side set all bits of L to be 1 if (z == 1) { // From (i+1)th bit, all bits // of L changed to be 1 v1.remove(i); v1.add(i,1); } } for (i = 0; i < v2.size(); i++) { v3.add(v2.get(i) | v1.get(i)); } for (i = 0; i < v2.size(); i++) { if (v3.get(i) == 1) { ans += cnt; } cnt *= 2; } return ans; } // Driver code public static void main(String []args) { int L = 10, R = 20; System.out.println(max_bitwise_or(L, R)); } } // This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach # Function to return the maximum bitwise # OR of any pair from the given range def max_bitwise_or(L, R): v1 = [] v2 = [] v3 = [] z = 0 i = 0 ans = 0 cnt = 1 # Converting L to its binary representation while (L > 0): v1.append(L % 2) L = L // 2 # Converting R to its binary representation while (R > 0): v2.append(R % 2) R = R // 2 # In order to make the number # of bits of L and R same while (len(v1) != len(v2)): # Push 0 to the MSB v1.append(0) for i in range(len(v2) - 1, -1, -1): # When ith bit of R is 1 # and ith bit of L is 0 if (v2[i] == 1 and v1[i] == 0 and z == 0): z = 1 continue # From MSB side set all bits of L to be 1 if (z == 1): # From (i+1)th bit, all bits # of L changed to be 1 v1[i] = 1 for i in range(len(v2)): v3.append(v2[i] | v1[i]) for i in range(len(v2)): if (v3[i] == 1): ans += cnt cnt *= 2 return ans # Driver code L = 10 R = 20 print(max_bitwise_or(L, R)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to return the maximum bitwise // OR of any pair from the given range static int max_bitwise_or(int L, int R) { List<int> v1 = new List<int>(), v2 = new List<int>(), v3 = new List<int>(); int z = 0, i, ans = 0, cnt = 1; // Converting L to its binary representation while (L > 0) { v1.Add(L % 2); L = L / 2; } // Converting R to its binary representation while (R > 0) { v2.Add(R % 2); R = R / 2; } // In order to make the number // of bits of L and R same while (v1.Count != v2.Count) { // Push 0 to the MSB v1.Add(0); } for (i = v2.Count - 1; i >= 0; i--) { // When ith bit of R is 1 // and ith bit of L is 0 if (v2[i] == 1 && v1[i] == 0 && z == 0) { z = 1; continue; } // From MSB side set all bits of L to be 1 if (z == 1) { // From (i+1)th bit, all bits // of L changed to be 1 v1.RemoveAt(i); v1.Insert(i, 1); } } for (i = 0; i < v2.Count; i++) { v3.Add(v2[i] | v1[i]); } for (i = 0; i < v2.Count; i++) { if (v3[i] == 1) { ans += cnt; } cnt *= 2; } return ans; } // Driver code public static void Main(String []args) { int L = 10, R = 20; Console.WriteLine(max_bitwise_or(L, R)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // JavaScript implementation of the approach // Function to return the maximum bitwise // OR of any pair from the given range function max_bitwise_or(L, R) { let v1 = [], v2 = [], v3 = []; let z = 0, i, ans = 0, cnt = 1; // Converting L to its binary representation while (L > 0) { v1.push(L % 2); L = parseInt(L / 2); } // Converting R to its binary representation while (R > 0) { v2.push(R % 2); R = parseInt(R / 2); } // In order to make the number // of bits of L and R same while (v1.length != v2.length) { // Push 0 to the MSB v1.push(0); } for (i = v2.length - 1; i >= 0; i--) { // When ith bit of R is 1 // and ith bit of L is 0 if (v2[i] == 1 && v1[i] == 0 && z == 0) { z = 1; continue; } // From MSB side set all bits of L to be 1 if (z == 1) { // From (i+1)th bit, all bits // of L changed to be 1 v1[i] = 1; } } for (i = 0; i < v2.length; i++) { v3.push(v2[i] | v1[i]); } for (i = 0; i < v2.length; i++) { if (v3[i] == 1) { ans += cnt; } cnt *= 2; } return ans; } // Driver code let L = 10, R = 20; document.write(max_bitwise_or(L, R)); </script>
31
Complejidad de tiempo: O(logR + logL)
Espacio auxiliar: O(logR + logL)
Publicación traducida automáticamente
Artículo escrito por sanchitagrawal429 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA