Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Least significant bit
3.
Approach
4.
Code in Python3
4.1.
Time Complexity
4.2.
Space Complexity
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author HET FADIA
2 upvotes
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This article aims to familiarise you with the bitwise operator problems and the concept of Least Significant Bit. 

To brush up on your knowledge of bitwise operators,  you can read the article Bitwise Operators on Coding Ninjas Studio.

Let’s see the problem statement in the next section.

Problem Statement

An array consisting of N positive integers is given. 

Find the maximum sum of Least Significant Bit of Bitwise OR of all possible N/2 pairs from the given array, i.e. arrange the elements of the array into N/2 elements to maximise the sum of the Least Significant Bit of the Bitwise OR of the N/2 pairs.

Before moving on to the examples, it's important to understand what does least significant bit imply as we will use this concept to build up the solution approach.

Note: Throughout this article, we will be using the term “lsb” which is a short form for Least Significant Bit.

Least significant bit

The least significant bit is the value of the number when all the set bits other than the rightmost bit in the binary representation of the number is set to 0. 

It can also be defined as the largest 2x(2 raised to x where x is non-negative integers) that divides the number.

Consider a few examples below:

1. Number = 10

The binary representation of 10 is 1010. So when only the rightmost set bit is kept in 1010 we get 0010 i.e. 2. So the lsb of 10 is 2.

We can also see that 20=1 and 21=2 divide 10 but not 22=4. So the answer is 21 i.e. 2

2. Number = 28

The binary representation of 28 is 11100. So when only the rightmost set bit is kept in 11100 we get 00100 i.e. 4. So the lsb of 28 is 4.

We can alternatively see that 4 i.e. 22 divides 28 but 23=8 does not divide 28. So the answer is 2 raised to 2 i.e. 4.

3. Number = 15

The binary representation of 15 is 1111. So when only the rightmost set bit is kept in 1111 we get 0001 i.e. 1. So lsb of 15 is 1.

 

Now, let us see a few of the examples of the problem statement:

1. arr=[3,5,7,10,11,16]

Output: 4 

Explanation: LSB(least significant bit) of 3,5,7,10,11,16 are 1,1,1,2,1,16 respectively.

So making the pairs (16,10), (11,7) and (5,3), the bitwise OR is 26, 15 and 7, respectively. Thus the Least Significant Bits are 2, 1 and 1, respectively. Thus the sum is 4.

2. arr=[2,3]

Output: 1

Explanation: Only one pair can be formed, i.e. (2,3). The bitwise OR is 3, and its lsb is 1. So the answer is 1.

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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)

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!!!

Previous article
Find the total number of subsequences having odd Bitwise OR values in the array
Next article
Find the next greater number formed with exactly two unique digits for each array element
Live masterclass