2275. Largest Combination With Bitwise AND Greater Than Zero

Given a list of integers, return the size of the largest combination of integers with a bitwise AND greater than 0.

So the question gives us a list of integers and we need to find the size of the largest combination of integers such that the bitwise AND of those integers gives us any integer greater than 0. We know one thing about the binary AND operator; It makes all the uncommon bits 0.

For ex ->

5&17

00101
10001
— — — -
00001

Now, our goal changes to: Find the largest list of integers that has at least one bit in common. Okay, we also know the max size of the number will fit in a 32 bit integer. Can we just create 32 length array to calculate how many integers in the list has that particular bit set? That will solve the question for us as we will know how many numbers has that bit set.

Lets take 8 bit numbers as example->

[16,17,71,62,12,24,14]
00010000 -> 16
00010001 -> 17
01000111 -> 71
00111110 -> 62
00001100 -> 12
00011000 -> 24
00001110 -> 14
set_bit_count_array = [0,0,0,0,0,0,0,0] // size of array is 8

Lets count how many numbers set a particular bit. If we take 16,
it sets the 5th bit and so on. So now array becomes.
[2,2,4,4,2,1]
Now we know there are at max 4 numbers which share a bit and if we do 
bitwise AND operations on those nums, the answer wont be 0 as that bit will 
still be set.

This answers our question.
Code:

class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        vector<int> bitsSetCount(32, 0);
        int mx = 0;
        for (int candidate: candidates) {
            for (int i = 0; i < 32; i++) {
                if ((candidate >> i) & 1)
                    bitsSetCount[i]++;
            }
        }

        for (int bit: bitsSetCount) {
            mx = max(bit, mx);
            cout << bit << " ";
        }
        cout << "\n";

        return mx;
    }
};

Thanks.