2275. Largest Combination With Bitwise AND Greater Than Zero

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

• For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.
• Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.

Return the size of the largest combination of candidates with a bitwise AND greater than 0.

Example 1:

Input: candidates = [16,17,71,62,12,24,14]
Output: 4
Explanation: The combination [16,17,62,24] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0.
The size of the combination is 4.
It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0.
Note that more than one combination may have the largest size.
For example, the combination [62,12,24,14] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.

Example 2:

Input: candidates = [8,8]
Output: 2
Explanation: The largest combination [8,8] has a bitwise AND of 8 & 8 = 8 > 0.
The size of the combination is 2, so we return 2.

Constraints:

• 1 <= candidates.length <= 105
• 1 <= candidates[i] <= 107

Approach 01:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        constexpr int maxBitPosition = 24;
        int maxCount = 0;

        for (int bitPosition = 0; bitPosition < maxBitPosition; ++bitPosition) {
            int currentBitCount = 0;
            for (const int candidate : candidates) {
                if (candidate >> bitPosition & 1)
                    ++currentBitCount;
            }
            maxCount = max(maxCount, currentBitCount);
        }

        return maxCount;
    }
};

from typing import List

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        maxBitPosition = 24
        maxCount = 0

        for bitPosition in range(maxBitPosition):
            currentBitCount = 0
            for candidate in candidates:
                if (candidate >> bitPosition) & 1:
                    currentBitCount += 1
            maxCount = max(maxCount, currentBitCount)

        return maxCount

Time Complexity

• Outer Loop over Bit Positions:

  The outer loop iterates over maxBitPosition, which is a constant value (24). This part of the function has \( O(1) \) complexity, as it doesn’t depend on the size of the input.

• Inner Loop over Candidates:

  For each bit position, the inner loop iterates over all candidates (size \( N \)). Checking the specific bit of each candidate takes \( O(1) \) time, so the inner loop is \( O(N) \).

• Overall Time Complexity:

  The time complexity is \( O(N) \), as the outer loop is constant and the inner loop iterates \( N \) times for each bit position.

Space Complexity

• Auxiliary Variables:

  The function uses a fixed number of variables (e.g., maxCount and currentBitCount), all of which have \( O(1) \) space complexity.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \), as only a fixed amount of extra space is required regardless of the input size.