Problem Description
Given an array arr[] of N positive elements. The task is to find the Maximum AND Value generated by any pair(arri, arrj) from the array such that i != j. Note: AND is bitwise ‘&’ operator.
geeksforgeeks
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution{
// Function for finding maximum AND value.
public static int maxAND (int arr[], int N) {
//Initialize
int ans = 0;
//Loop through all the bits
for(int i=30; i>=0; i--){
//Initialize count of bits which are set at position i
int count = 0;
//Loop through all the elements in the array and check if the ith position bit is set
for(int j=0; j<N; j++){
if(checkBit(arr[j], i)){
//Increase the count if it's set
count++;
}
}
//The question asks us to find the max sum possible for a pair of elements in the array
//The answer's bit will be set ONLY IF BOTH THE ELEMENTS HAVE THAT BIT POSITION SET
//So, IFF there are at least two numbers in the list which have the current bit position set, we can consider that
//If one number is set, other is not set, their AND will be 0 for that position
//The other important thing is, we started loop from MSB because it has the maximum contribution to the overall sum.
if(count >= 2){
//If we have at least 2 numbers which have current bit position as set, then our answer must also have the bit set in this position
//So, we add 2^i or 1<<i to the answer
ans = ans + (1<<i);
//At this point, we can be sure that we do not need to consider other numbers which do not have bit set at the current position (because we have already got 2 numbers, which when taken together will result in higher sum)
//So, we loop through the numbers and set the number to 0 if their current bit position is 0. We are basically getting rid of those numbers since they will not yield higher sum, even if rest of the right bits are set
for(int k=0; k<N; k++){
if(!checkBit(arr[k], i)){
arr[k] = 0;
}
}
}
}
return ans;
}
public static boolean checkBit(int n, int pos){
n = n>>>pos;
return (n&1)==1;
}
}