Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code in Python
3.2.
Code in C++
3.3.
Code in Java
3.4.
Time Complexity
3.5.
Space Complexity
4.
Frequently Asked Questions
5.
Key Takeaways
Last Updated: Mar 27, 2024

Find the size of the largest subset with bitwise AND greater than their bitwise XOR

Author HET FADIA
0 upvote
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 on subsets(a subset is any possible combination of the original array) of an array

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

Find the size of the largest subset, i.e. largest possible combination of the array for which the bitwise AND is greater than the bitwise XOR.

A few examples are as follows:

1. arr=[1,14]

Output: 1

As there are no subsets whose bitwise AND is greater than the bitwise XOR

2. arr=[4,5,6]

Output: 2

The subset is (4, 5) whose bitwise AND is 4 and the bitwise XOR is 1.

Another such subset is (4, 6), whose bitwise AND is 4 and the bitwise XOR is 2.

Since the maximum size is still 2, the answer is 2.

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

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)

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;
}

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));
   }
}

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

 

Previous article
Find the maximum product of Bitwise AND and Bitwise OR of K-size subarray
Next article
Find the total number of subsequences having odd Bitwise AND values in the array
Live masterclass