Created
October 29, 2020 22:39
-
-
Save Ch-sriram/030d832d89a5d647309a2e36234be325 to your computer and use it in GitHub Desktop.
Maximum AND Value [TC: O(32*N); SC: O(1)]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Problem Link: https://practice.geeksforgeeks.org/problems/maximum-and-value2637/1 | |
int checkBit(int pattern, int arr[], int n) { | |
int count = 0; | |
for(int i = 0; i < n; ++i) | |
if((pattern & arr[i]) == pattern) | |
++count; | |
return count; | |
} | |
// Function for finding maximum and value pair | |
int maxAND (int arr[], int n) { | |
int maxEle = INT_MIN; | |
for(int i = 0; i < n; ++i) | |
maxEle = max(maxEle, arr[i]); | |
int MSB = 0; | |
for(int i = 0; i < 32; ++i) | |
if((maxEle >> i) & 1) | |
MSB = i; | |
int res = 0, count; | |
for(int bit = MSB; bit >= 0; --bit) { | |
count = checkBit(res | (1 << bit), arr, n); | |
if(count >= 2) res |= (1 << bit); | |
} | |
return res; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Problem Link