Approach
Our approach is to find the bitwise AND and the Bitwise XOR for all possible subsets and update the answer whenever we find a larger subset.
Thus our idea is to use recursion to solve the problem. In the recursion, we will keep the note of bitwise XOR and bitwise AND of the subset so that whenever we add a new element, we can get the bitwise XOR and bitwise AND of the subset in O(1) time.
We will also keep a variable say, counted, to check the size of the current subset. Whenever the bitwise AND > bitwise XOR for that subset, we will update the answer to max(answer, counted).
Code in Python
Here is the recursive 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
Code in C++
// C++ implementation
#include <bits/stdc++.h>
using namespace std;
// Recursive function
int maxSizeSubset(int* arr, int N, int bitwiseXOR, int bitwiseAND, int i, int len = 0)
{
// Stores the maximum length of subset
int ans = INT_MIN;
// Updating the ans
if (bitwiseAND > bitwiseXOR)
ans = len;
// Base Case
if (i == N)
return ans;
// Recursive call excluding the ith element of the array
ans = max(ans, maxSizeSubset(arr, N, bitwiseXOR, bitwiseAND, i + 1, len));
// Recursive call by including the ith element of the array
ans = max(ans, maxSizeSubset(arr, N,(arr[i] ^ bitwiseXOR),(arr[i] & bitwiseAND), i + 1, len + 1));
return ans;
}
//Main function( Driver Code)
int main()
{
int arr[] = {3,5,7,10,11,16};
int N = sizeof(arr) / sizeof(arr[0]);
// printing the ans
cout << maxSizeSubset(arr, N, 0, pow(2, 10) - 1, 0);
return 0;
}
You can also try this code with Online C++ Compiler
Code in Java
// Java program for the above approach
import java.util.*;
class Main{
// Recursive function
static int maxSizeSubset(int[] arr, int N, int bitwiseXOR, int bitwiseAND, int i, int len)
{
// Stores the answer(that is maximum length of subset)
int ans = Integer.MIN_VALUE;
// Update ans
if (bitwiseAND > bitwiseXOR)
ans = len;
// Base Case
if (i == N)
return ans;
// Recursive call excluding the ith element of the array
ans = Math.max(ans, maxSizeSubset(arr, N, bitwiseXOR, bitwiseAND, i + 1, len));
// Recursive call including the ith element of the array
ans = Math.max(ans, maxSizeSubset(arr, N,(arr[i] ^ bitwiseXOR), (arr[i] & bitwiseAND), i + 1, len + 1));
// Return the ans
return ans;
}
// Driver Code
public static void main (String[] args) {
int arr[] = {3,5,7,10,11,16};
int N = arr.length;
//printing the answer
System.out.println(maxSizeSubset(arr, N, 0, (int)Math.pow(2, 10) - 1, 0, 0));
}
}
You can also try this code with Online Java Compiler
Output
2
Time Complexity
The time complexity of the above python3 code is O(2^N), i.e. exponential.
Here N is the size of the array.
The time complexity looks like the full binary tree having depth N. This is because each arr[index] is taken in one case while skipped in another case. So for each index, it calls two subcases.
Figure 1. The image depicts the recursion tree for the above code.
Source: link
Here, we calculate the bitwise And and Bitwise Xor for every subset of the given array. Since the total subsets of an array are 2^N, the time complexity is O(2^N).
Alternatively, we can also see that there are two cases for each index
- We include the arr[index] and calculate the answer
- We do not include the arr[index] and calculate the answer
Thus 2 * 2 * 2 … * 2 N times which comes out to be O(2^N).
Solving it, we get T(n) = O(2^N).
Space Complexity
The space complexity of the above code is O(N).
At any point in time, the maximum stack depth is O(N).
Read about Bitwise Operators in C and Euclid GCD Algorithm 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.
The code given here is recursive. It calls itself multiple times on a smaller subset to solve the problem. In each recursion, the answer is updated and returned. There is also a base case when the index is equal to the size of the array. In this case, we update and return the answer.
Check out this problem - Longest Subarray With Sum K
You can read more about recursion here.
Happy Learning!!!
85+ registered 