Maximize sum of LSBs of Bitwise OR of all possible N/2 pairs from given Array

Approach

First of all, we will need to know the lsb of each of the array elements. So we will make a function get_lsb to get the lsb of each element.

Let us consider two elements e1 and e2, and their lsbs are lsb1 and lsb2, respectively. Then the lsb of bitwise OR of them, i.e. e1 | e2 will have lsb = min(lsb1,lsb2). 

For example, 10 and 16 have lsb 2 and 16 respectively, but their bitwise OR, i.e. 26, will have lsb min(2,16) = 2.

So we can sort the array in descending order and make pairs in the following way

1. The first and second elements in the reverse sorted array will form pairs,

2. The third and fourth elements in the reverse sorted array will form pairs, and so on.

Thus the answer will have the sum of lsb of 2nd, 4th, 6th and so on elements. 

Now suppose the lsb array is [9,4,2,1].

The bitwise OR of two elements having lsb 9 and 4 will also have lsb 4, so our answer will be 4+1 = 5.

So our approach will be to find the LSB's of all elements and store it in an array. Then sort the array in descending order. Then find the sum of 2nd, 4th, 6th and so on elements of the lsb_array(1 based). 

The final sum obtained is our answer.

Code in Python3

Here is the code for the problem in python3.

def get_lsb(element):
    # we get the length of total bits in the number
    ele_len=element.bit_length()
    for i in range(ele_len):
        if element&(1<<i):
            # if the ith bit is set then Bitwise AND of 1<<i and element will be positive
            return 1<<i
    # if none of the bit is set then we return 0
    return 0
def max_sum_of_lsb(arr):
    # we get the lsb of each element and make the array named lsb_array
    lsb_array=[get_lsb(element) for element in arr]
    lsb_array.sort(reverse=True)


    """
    Here we have sorted reverse because bitwise OR of two elements having lsb x and y will have lsb min(x,y)
    So for each two larger elements the answer will have the lsb of 2nd , 4th , 6th.... elements
    Now suppose the lsb array is [9,4,2,1]
    Now the bitwise OR of two element having lsb 9 and 4 will also have lsb 4
    so our answer will be 4+1 = 5
    """
    answer=0
    for i in range(1,len(lsb_array),2):
        answer+=lsb_array[i]
    return answer


arr=[3,5,7,10,11,16]
answer=max_sum_of_lsb(arr)
print(answer)

You can also try this code with Online Python Compiler

Run Code

Output

4

Time Complexity

The time complexity of the above solution will be O(N*logN), where N is the array's length.

The get_lsb function will take time O(log2(element)) or O(bit_length) of the element.

For example for element 1000, the time taken will be ceil(log2(1000)) =11.

Here we are talking about integers and long long numbers so that the maximum bit_length will be 64.

So, the time taken by the get_lsb function for each array element will be 64*N = O(N).

Then we sort the array in descending order which takes O(N*log N) time.

Finally, we calculate the answer, which takes O(N) time as we traverse the array only once.

Thus time complexity will be max(O(N), O(N*log N), O(N)) which is O(N*logN).

Space Complexity

The space complexity of the above code is O(N).

We make an lsb array of size N, which takes O(N) space.

Sorting lsb_array will take O(logN) space complexity(using intro sort).

Thus, the space used will be O(N) as it dominates.

Read about Bitwise Operators in C here.

Frequently Asked Questions

1. How to implement the get_lsb function?

The get_lsb function gives the least significant bit in the provided number. For example, get_lsb(24) should give 8 because 24 in binary is 11000, so the least significant bit is the last 4th 1 (1000 in 11000). 1000 in binary has a value of 8.

The program keeps on checking the first set bit and then returns 1<<i.

Here 1<<i is the left shift operation. Thus in 24, (1<<3)&24 = 8&24= 8 will be true and 8 will be returned. If there is no set bit, we return 0 because 0 is the only non-negative integer having no set bits. 

2. What is the bit_length used in the program?

The bit_length is an inbuilt python function that gives the number of bits. For 8, the bit_length will be 4 because the binary form of 8 is 1000, which consists of 4 bits.

3. Why are we sorting the lsb_array in reverse order?

The bitwise OR of two elements having lsb x and y will have lsb min(x,y). 

We have to arrange the elements to maximise the sum of lsbs of bitwise OR of N/2 pairs.

Thus we sort lsb_array in descending order and take the sum of 2nd, 4th, 6th and so on elements of the lsb array.

Key Takeaways

The article helps us to understand the bitwise operators in python. You can also copy the code and run it on your system on multiple inputs to understand the approach better.

We have used the get_lsb function here because we have to find the lsb of each array element. Then we sorted the lsb_array in descending order(you can read about sorting techniques here). Finally, we get the answer, and we print it.

Check out the blog Bit Manipulation for Competitive Programming to learn more about the uses and techniques of bit manipulation.

Check out this problem - Pair Sum In Array.

Happy Learning!!!