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.

• Brute Force
• Optimized approach

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

C++

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;
}

Java

Written by @AmruthaPariprolu

import java.util.*;

public class BruteForceSolution {
    public int largestCombinationBruteForce(int[] candidates) {
        int n = candidates.length;
        int max_size = 0;

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

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

            if (bitwiseAnd > 0) {
                max_size = Math.max(max_size, count);
            }
        }

        return max_size;
    }
}

Python

Written by @AmruthaPariprolu

import java.util.*;

public class BruteForceSolution {
    public int largestCombinationBruteForce(int[] candidates) {
        int n = candidates.length;
        int max_size = 0;

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

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

            if (bitwiseAnd > 0) {
                max_size = Math.max(max_size, count);
            }
        }

        return max_size;
    }
}

Complexity Analysis

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

---

Authors:

Loading...