Hey everyone, let's learn about this amazing question, Maximum AND value of a pair in an array. We will be discussing the complete theory part that you will need to solve this question in detail. There are many solutions videos available on Youtube for this question but they are way too long and boring. I will make sure after reading this article you get a clear understanding of the concept.

What do we have to do in the question?

The question is asking you to find Maximum AND value of a pair in an array, for example, let's consider an array.

We have to find AND operation for each pair in this array and check that which pair gives us the maximum value on doing AND operation. So, we have to check like that,

1 & 2, 1 & 3, 1 & 4, 1 & 5, 1 & 6 and so on.

Note: We don't find AND of a number with itself, as it would give the same number. 1 & 1 = 1

For those who don't know what AND operation do?

It actually works on a bitwise approach; it compares every bit of a number with the corresponding bit in the other number.

If both the bits are set (set bits means bits have value 1), it returns 1 in answer, If both the bits are 0 or if one bit is zero and another bit is 1, it returns 0 in the answer.

Solution Approach

This question can easily be solved using an iterative approach i.e. by using two for loops. The code for the same is provided below:

// Java Program to find maximum
// AND value of a pair
import java.lang.*;
import java.util.*;

public class Codengine {

    // Function for finding maximum
    // and value pair
    static int maxAND(int arr[], int n)
    {
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if( ( arr[i] & arr[j]) > res ){
                res = (arr[i] & arr[j]);
}

        return res;
    }

    // driver function
    public static void main(String argc[])
    {
        int arr[] = { 4, 8, 6, 2 };
        int n = arr.length;
        System.out.println("Maximum AND Value = "
                        + maxAND(arr, n));
    }
}

The above program will run two loops and find the AND value of each existing pair in array and hence, it will update the res variable with that value of the AND value of a pair would be greater than the AND value of previous pair. Pretty Simple Right!!!

But, just think about the time complexity of this program, we have two loops, one nested inside the other. The time complexity would be O(n^2).

Can we solve this question with a better time complexity??

Yes, we can do it using Bitwise operators. Now you need to pay some extra attention to the words, as I am going to discuss some important points regarding the bitwise approach.

1. We will consider that the integers are represented in 32 bits format. (As in Java).
2. You should know about the conversion binary to decimal numbers.

In any binary number the Left most bit is the most significant bit (MSB)(Unsigned) and the Right most bit is the least significant bit (LSB).

Now if the MSB is set (i.e. its value is 1) Then, it would have a larger value than all other numbers in which the MSB is not set. Similarly, if the bit, just next to the MSB is set, then the number will have greater value than all other numbers in which that bit is not set.

Let's understand this thing with an example.

In the above example two numbers are given in 4-bit representation and the left most bit is the MSB. Now in the first number the MSB is set but in the second number the MSB is not set.

You can clearly observe that, when the MSB is set then the value of that bit is (2^3) *1 i.e. 8.

(You should know binary to decimal conversion to understand this).

In the second number the MSB is not set and the value of MSB is (2^3) *0 i.e. 0. Similarly, we can check for every consecutive bit from the left to know which number is greater.

If the left most bit is set, it can produce a maximum value for a number.

Finally, the theory part is over, let's apply what we understood above to the problem and get the solution.

We know that in AND operation, the result is 1, only when both the corresponding bits in the number are 1.

Pay attention here:

We will consider the 32 bits representation integers, then we should start check the 31st bit of every number (i.e. MSB) whether it's set or not.

If there are two such elements whose 31st bit is set, we can take the 31st bit of our result as set bit, because when we will do the AND of those two numbers, both the numbers would have their 31st bit as set and then they will produce a set bit in result at 31st position as AND operation gives 1 when both the number have corresponding bit as set. See the example given below.

Similarly, we will check for the 30th bit, 29th bit, 28th bit, 27th bit and so on till the last bit that is 0th bit.

If these bits are set for two or more numbers, we will set them in our result too. The illustrations below will help you to understand the steps written above.

Now we know how to check a number for a particular bit, we will check all the numbers in the array for 31st bit, if we find two or more numbers with the 31st bit set in them, then we will set the 31st bit in our result. Similarly, we will check each bit of every element present in the array and if two or more numbers are found to have the same bit set in them, we will set that bit our result.

Finally, we completed the concept now it's time to code it:

import java.lang.*;
import java.util.*;

public class Codengine {

    // Function to check whether a bit is set or not in the number
    static int checkBit(int pattern, int arr[], int n)
    {
        int count = 0;
        for (int i = 0; i < n; i++)
            if ((pattern & arr[i]) == pattern) 
//pattern is nothing but (1 << bit)
                count++;
        return count;
    }

    // Function for finding maximum and value pair
    static int maxAND(int arr[], int n)
    {
        int res = 0, count;

        // iterate over total of 32bits
        // from msb to lsb
        for (int bit = 31; bit >= 0; bit--) {
            // find the count of element
            // having set msb
            count = checkBit(res | (1 << bit), arr, n);

            // if count >= 2 set particular
            // bit in result
            if (count >= 2)
                res = res | (1 << bit);
        }

        return res;
    }

    // driver function
    public static void main(String argc[])
    {
        int arr[] = { 4, 8, 6, 2 };
        int n = arr.length;
        System.out.println("Maximum AND Value = "
                           + maxAND(arr, n));
    }
}

We have used two methods, one to determine whether the bit is set or not, and the second method to find AND of two numbers and produces the result.

The parameter res | (1<<bit) has been passed as an argument in check function, this piece of code actually keeps the previously set bits in the result as set and keeps adding new set bits if the required conditions are fulfilled.

I hope this article helped you to learn the concept in-depth. Share this article if you find it useful, I would love to receive your suggestions and feedback over this article.

Thank You

Article Crafted with Love ❤️ by Codengine.