Given an array Arr of non-negative integers of size N, the task is to find the maximum possible OR between two numbers present in the array.
Example:
Input: Arr = {25, 10, 2, 8, 5, 3}
Output: 29Input: Arr = {1, 2, 3, 4, 5, 6, 7}
Output: 7
Naive Approach: A Simple Solution is to generate all pairs of the given array and compute OR of the pairs. Finally, return the maximum XOR value.
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Better Approach: The approach is based on below Bitwise observation:
- If we set all bits of current arr[i], i.e. lets say arr[i]=10 (1010),
- and we change it to 15 (1111),
- and the current max OR calculated so far is greater than 15,
- then we dont need to check for arr[i], as it wont affect our ans.
This seems like a small change but it will reduce the time significantly.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to return the maximum ORint maxOR(vector<int>& nums){ int n = nums.size(); int ans = 0; for (int i = 0; i < n; i++) { if (ans >= pow( 2, floor(log2(nums[i]) + 1)) - 1) continue; for (int j = 0; j < n; j++) { if (i != j) ans = max(ans, nums[i] | nums[j]); } } return ans;}// Driver Codeint main(){ vector<int> arr = { 1, 2, 3, 4, 5, 6, 7 }; cout << maxOR(arr) << endl; return 0;} |
Java
// JAVA implementation of the above approachimport java.util.*;class GFG { // Function to return the maximum OR public static int maxOR(ArrayList<Integer> nums) { int n = nums.size(); int ans = 0; for (int i = 0; i < n; i++) { if (ans >= Math.pow(2, Math.floor( Math.log(nums.get(i)) + 1)) - 1) continue; for (int j = 0; j < n; j++) { if (i != j) ans = Math.max(ans, nums.get(i) | nums.get(j)); } } return ans; } // Driver Code public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>( Arrays.asList(1, 2, 3, 4, 5, 6, 7)); System.out.println(maxOR(arr)); }}// This code is contributed by Taranpreet |
Python3
# Python code for the above approach# Function to return the maximum ORfrom math import pow, floor, log2def maxOR(nums): n = len(nums) ans = 0 for i in range(n): if (ans >= pow(2, floor(log2(nums[i]) + 1)) - 1): continue for j in range(n): if (i != j): ans = max(ans, nums[i] | nums[j]) return ans# Driver Codearr = [1, 2, 3, 4, 5, 6, 7]print(maxOR(arr))# This code is contributed by gfgking |
C#
// C# implementation of the above approachusing System;class GFG{ // Function to return the maximum OR public static int maxOR(int[] nums) { int n = nums.Length; int ans = 0; for (int i = 0; i < n; i++) { if (ans >= Math.Pow(2, Math.Floor( Math.Log(nums[i]) + 1)) - 1) continue; for (int j = 0; j < n; j++) { if (i != j) ans = Math.Max(ans, nums[i] | nums[j]); } } return ans; } // Driver Code public static void Main() { int[] arr = { 1, 2, 3, 4, 5, 6, 7 }; Console.Write(maxOR(arr)); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script> // JavaScript code for the above approach // Function to return the maximum OR function maxOR(nums) { let n = nums.length; let ans = 0; for (let i = 0; i < n; i++) { if (ans >= Math.pow( 2, Math.floor(Math.log2(nums[i]) + 1)) - 1) continue; for (let j = 0; j < n; j++) { if (i != j) ans = Math.max(ans, nums[i] | nums[j]); } } return ans; } // Driver Code let arr = [1, 2, 3, 4, 5, 6, 7]; document.write(maxOR(arr) + '<br>'); // This code is contributed by Potta Lokesh </script> |
Output
7
Time Complexity: O(N^2)
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!
