Given a range [L, R], the task is to find the maximum bitwise OR of some pair (a, b) from the given range.
Examples:
Input: L = 10, R = 20
Output: 31
Input: L = 56, R = 77
Output: 127
Approach: First, convert both the given integers L and R to their binary representations. Now, If L has less number of bits than R then push zero to the MSB side of L to make the number of bits of both L and R to be equal.
Now from the MSB side compare the individual bits of both L and R. As R is greater than L, we will find the case when ith bit of R is 1 and ith bit of L is 0. So after ith bit, make all the bits of L to be 1. This ensures that the modifications done in the bits of L will not exceed R, so it will be between L and R only. And doing this also ensures maximum bitwise or.
Below is the implementation of the above approach:
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 rangelong 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 codeint main(){ long long int L = 10, R = 20; cout << max_bitwise_or(L, R); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG {// Function to return the maximum bitwise// OR of any pair from the given rangestatic 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 codepublic 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 rangedef 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 codeL = 10R = 20print(max_bitwise_or(L, R))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG {// Function to return the maximum bitwise// OR of any pair from the given rangestatic 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 codepublic 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 rangefunction 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> |
Output:
31
Time Complexity: O(logR + logL)
Auxiliary Space: O(logR + logL)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
