4 elements that form the maximum Bitwise AND

help
, , , ,
1

Given an array, return a subsequence of length 4, whose elements when ANDed together have the highest value.

We have an array containing N numbers (N > 4). We have to find out the 4 numbers which when ANDed together, return the maximum value.

Example 1:

Input:
{10, 20, 4, 15, 14}

Output:
4

Explanation:
15 & 4 & 20 & 14 = 4.

Example 2:

Input:
{2, 2, 2, 2, 1}

Output:
2

Explanation:
2 & 2 & 2 & 2 = 2.

2

It’s greedy.
Check if most significant bit(left most) is 1 in at least 4 of them. If yes then select those numbers (having MSB = 1) and remove rest of them and also remove left most bit.
Or if there are less than 4 numbers having most significant bit 1 then keep all of them and remove most significant bit from all of them. And repeat untill there are 0 bits left.
This way you’ll get solution in N*log(K) where K is the MAX value of input number.

2 Likes
3

@l_returns

It would be really great if you could please be a bit more elaborate. And if possible, come up with a code snippet.

4

What is not clear in above message ?
Nope I won’t give you code snippet. I believe it’s better if you write code on your own.

1 Like
5

PS: Edited OP and added examples. Please check accordingly.

@l_returns I understood what you said, but I’m not sure if you are getting the question correct. I’m editing the OP to make the question more clear. Also, I have written down the code snippet based on your answer, but I’m not able to figure out how this will get me the desired result.

Also you mention MSB to be the right most one, but LSB is the right most one. MSB is the left most one.

#include<bits/stdc++.h>

using namespace std;

bool isLsbOne(int n)
{
	if (n & 1)
		return true;
	return false;
}

vector<int> retOddArray(vector<int> &a)
{
	vector<int> b;
	for (int i=0; i<a.size(); i++)
	{
		if (isLsbOne(i))
			b.push_back(a[i] >> 1);
		a[i] >>= 1;
	}
	if (b.size() >= 4)
		return b;
	return retOddArray(a);
}

int main()
{
	int n, input;
	cin>>n;
	vector<int> v;
	for (int i=0; i<n; i++)
	{
		cin>>input;
		v.push_back(input);
	}
	vector<int> a = retOddArray(v);
	sort(a.begin(), a.end(), greater<int>());
	int b = a[0] & a[1] & a[2] & a[3];
	cout<<b<<endl;
	return 0;
}
6

I think I understood question correctly.
Sorry my bad I meant left most bit i.e. MSB.
Edited.
And please modify this in your code as well. Check left most bit. That is if numbers are upto 1024 then start with 10th position (9th if we consider 0 based indexing) and then 9th and so on…
Also if you just discard all bits then answer will be 0. Construct your answer parallelly.
If you find more than 4 numbers having current bit = 1 then your ans will have 1 at that position. And if you do not find 4 Such numbers then answer will have 0 at that bit position.
Also don’t just return directly when you get more than 4 numbers having current bit 1
Keep repeating until all elements become 0.
That is if numbers can be upto 1024 then you will have to repeat the process for 10 times.

2 Likes