Largest Combination With Bitwise AND Greater Than Zero

Leetcode Problem:

• Largest Combination With Bitwise AND Greater Than Zero

Summary

• Find the size of the largest combination of elements in the candidates array with a bitwise AND greater than 0.

Approach

• The approach used is to generate all possible combinations of elements in the candidates array by iterating over all possible bitmasks (0-24)
• For each bitmask, count the number of elements in the candidates array that have the corresponding bit set
• The maximum count is the size of the largest combination with a bitwise AND greater than 0.

Complexity

• O(n * 24) where n is the number of elements in the candidates array

Explanation

• The solution iterates over all possible bitmasks (0-24) and for each bitmask, it counts the number of elements in the candidates array that have the corresponding bit set
• This is done by using a bitwise AND operation between the bitmask and each element in the candidates array
• If the result is greater than 0, it means the bit is set in the element, so the count is incremented
• The maximum count is updated if a larger count is found
• The solution returns the maximum count as the size of the largest combination with a bitwise AND greater than 0.

Solution Code:

class Solution {
public:
    int largestCombination(vector& candidates) {
        int maxCnt = 0;
        for(int i = 0 ; i < 24; i++){
            int mask = 1 << i;
            int cnt = 0;
            for(int j = 0 ; j < candidates.size(); j++){
                if((candidates[j] & mask) > 0){
                    cnt++;
                }
            }
            maxCnt = max(maxCnt, cnt);
        }
        return maxCnt;
    }
};