Skip to main content

Largest Combination With Bitwise AND Greater Than Zero

Problem Statement​

In this tutorial, we will solve the Largest Combination With Bitwise AND Greater Than Zero problem . We will provide the implementation of the solution in Python, Java, and C++.

Problem Description​

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.

Examples​

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

Solution of Given Problem​

Intuition and Approach​

The problem can be solved using a brute force approach or an optimized Technique.

Approach 1:Brute Force (Naive)​

Brute Force Approach: The brute force approach would involve evaluating the bitwise AND for every possible combination of the given candidates. However, given the constraints, this approach is impractical due to its high computational complexity.

Codes in Different Languages​

Written by @AmruthaPariprolu
#include <vector>
#include <algorithm>

int largestCombinationBruteForce(std::vector<int>& candidates) {
int n = candidates.size();
int max_size = 0;

// Iterate over all possible combinations of candidates
for (int mask = 1; mask < (1 << n); ++mask) {
int bitwise_and = -1; // Initialize with all bits set
int count = 0;

for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
if (bitwise_and == -1) {
bitwise_and = candidates[i];
} else {
bitwise_and &= candidates[i];
}
++count;
}
}

if (bitwise_and > 0) {
max_size = std::max(max_size, count);
}
}

return max_size;
}



Complexity Analysis​

  • Time Complexity: O(2n∗n)O(2^n*n)
  • Evaluates all possible subsets (2^n) and performs bitwise AND operations on each subset.
  • Space Complexity: O(1)O(1)
  • Uses a constant amount of extra space.

Authors:

Loading...