Given an array arr[] containing N positive integers, the task is to find the maximum bitwise OR value of a pair in the given array without using the Bitwise OR operator.
Examples:
Input: arr[] = {3, 6, 8, 16}
Output: 24
Explanation:
The pair giving maximum OR value is (8, 16) => 8|16 = 24
Input: arr[] = {8, 7, 3, 12}
Output: 15
Explanation:
There are more than one pair giving us the maximum OR value. One among them => 8|7 = 15
Approach: The idea is to find the two numbers which have the most count of set bits at distinct indices. In this way, the resultant number will have all those indices as a set bit, and this can be done without using the OR operator.
- Find out the maximum element in the array and then find the particular element in the remaining array that will have the set bit at the indexes where the maximum element has an unset bit.
- To maximize our output we have to find such an element that will have a set bit in such a manner that will maximize our output.
- Calculate the complement of the maximum element in the array and find the maximum AND value with the other numbers.
- The maximum AND value of this complement with other array elements will give us the maximum unset bits that could be set in our answer due to other array elements.
- Adding maximum elements with this maximum AND value will give us our desired maximum OR value pair without using OR operation.
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// for any pair of the given array// without using bitwise OR operationint maxOR(int arr[], int n){ // find maximum element in the array int max_value = *max_element(arr, arr + n); int number_of_bits = floor(log2(max_value)) + 1; // finding complement will set // all unset bits in a number int complement = ((1 << number_of_bits) - 1) ^ max_value; int c = 0; // iterate through all other // array elements to find // maximum AND value for (int i = 0; i < n; i++) { if (arr[i] != max_value) { c = max(c, (complement & arr[i])); } } // c will give the maximum value // that could be added to max_value // to produce maximum OR value return (max_value + c);}// Driver codeint main(){ int arr[] = { 3, 6, 8, 16 }; int n = sizeof(arr) / sizeof(arr[0]); cout << maxOR(arr, n); return 0;} |
Java
// Java implementation // of the approachimport java.util.*;class GFG{// Function to return the maximum // bitwise OR for any pair of the // given array without using bitwise // OR operationstatic int maxOR(int arr[], int n){ // find maximum element in the array int max_value = Arrays.stream(arr).max().getAsInt(); int number_of_bits = (int)((Math.log(max_value))) + 2; // finding complement will set // all unset bits in a number int complement = ((1 << number_of_bits) - 1) ^ max_value; int c = 0; // iterate through all other // array elements to find // maximum AND value for (int i = 0; i < n; i++) { if (arr[i] != max_value) { c = Math.max(c, (complement & arr[i])); } } // c will give the maximum value // that could be added to max_value // to produce maximum OR value return (max_value + c);}// Driver codepublic static void main(String[] args){ int arr[] = {3, 6, 8, 16}; int n = arr.length; System.out.print(maxOR(arr, n));}}// This code is contributed by gauravrajput1 |
Python3
# Python3 implementation of the approachfrom math import log2, floor# Function to return the maximum bitwise OR# for any pair of the given array# without using bitwise OR operationdef maxOR(arr, n): # Find maximum element in the array max_value = max(arr) number_of_bits = floor(log2(max_value)) + 1 # Finding complement will set # all unset bits in a number complement = (((1 << number_of_bits) - 1) ^ max_value) c = 0 # Iterate through all other # array elements to find # maximum AND value for i in range(n): if (arr[i] != max_value): c = max(c, (complement & arr[i])) # c will give the maximum value # that could be added to max_value # to produce maximum OR value return (max_value + c)# Driver codeif __name__ == '__main__': arr = [3, 6, 8, 16] n = len(arr) print(maxOR(arr, n))# This code is contributed by Bhupendra_Singh |
C#
// C# program for the above approach using System;using System.Linq; class GFG{// Function to return the maximum // bitwise OR for any pair of the // given array without using bitwise // OR operationstatic int maxOR(int[] arr, int n){ // Find maximum element in the array int max_value = arr.Max(); int number_of_bits = (int)(Math.Log(max_value)) + 2; // Finding complement will set // all unset bits in a number int complement = ((1 << number_of_bits) - 1) ^ max_value; int c = 0; // Iterate through all other // array elements to find // maximum AND value for(int i = 0; i < n; i++) { if (arr[i] != max_value) { c = Math.Max(c, (complement & arr[i])); } } // c will give the maximum value // that could be added to max_value // to produce maximum OR value return (max_value + c);}// Driver codepublic static void Main(){ int[] arr = { 3, 6, 8, 16 }; int n = arr.Length; Console.Write(maxOR(arr, n));}}// This code is contributed by code_hunt |
Javascript
<script>// javascript implementation // of the approach // Function to return the maximum // bitwise OR for any pair of the // given array without using bitwise // OR operation function maxOR(arr , n) { // find maximum element in the array var max_value = Math.max.apply(Math,arr); var number_of_bits = parseInt( ((Math.log(max_value)))) + 2; // finding complement will set // all unset bits in a number var complement = ((1 << number_of_bits) - 1) ^ max_value; var c = 0; // iterate through all other // array elements to find // maximum AND value for (i = 0; i < n; i++) { if (arr[i] != max_value) { c = Math.max(c, (complement & arr[i])); } } // c will give the maximum value // that could be added to max_value // to produce maximum OR value return (max_value + c); } // Driver code var arr = [ 3, 6, 8, 16 ]; var n = arr.length; document.write(maxOR(arr, n));// This code is contributed by todaysgaurav</script> |
Output:
24
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
