Largest Combination With Bitwise AND Greater Than Zero

Largest Combination With Bitwise AND Greater Than Zero - Problem

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. Compute the bitwise AND for all possible combinations of elements in the candidates array.

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

Input & Output

Example 1 — Basic Case

$ Input: candidates = [16,17,71,62,12,24,14]

› Output: 4

💡 Note: The combination [16,17,24,30] has AND = 16 > 0. We can verify bit 4 is set in exactly 4 numbers, which is the maximum.

Example 2 — Small Array

$ Input: candidates = [8,8]

› Output: 2

💡 Note: Both numbers are identical, so we can pick both and their AND = 8 > 0.

Example 3 — No Common Bits

$ Input: candidates = [1,2,4,8]

› Output: 1

💡 Note: Each number has a unique bit set, so maximum combination size with AND > 0 is 1.

Constraints

1 ≤ candidates.length ≤ 10⁵
1 ≤ candidates[i] ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [16,17,71,62,12,24,14] of positive integers

Analyze Bits

Convert to binary and count bit position occurrences

Find Maximum

Largest count gives us the answer: 4

Key Takeaway

🎯 Key Insight: The largest valid combination will always share the most frequently occurring bit position

Asked in

f Meta 25 G Google 15

The key insight is that for a combination to have AND > 0, all numbers must share at least one common bit position. By counting how many numbers have each bit position set, we find the maximum possible combination size. Best approach uses bit manipulation in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Combinations	O(n × 2^n)	O(1)	Generate all possible combinations and check which ones have AND > 0
Bit Manipulation - Count Bit Positions	O(n)	O(1)	For each bit position, count how many numbers have that bit set

Brute Force - Generate All Combinations — Algorithm Steps

Generate all possible combinations using bit manipulation
For each combination, compute bitwise AND of all elements
Keep track of maximum size where AND > 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Use bit masks to generate all 2^n combinations

Compute AND

For each subset, calculate bitwise AND of all elements

Track Maximum

Keep the largest size where AND > 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* candidates, int n) {
    int maxSize = 0;
    
    // Try all possible combinations (2^n - 1, excluding empty set)
    for (int mask = 1; mask < (1 << n); mask++) {
        int currentAnd = -1;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                if (currentAnd == -1) {
                    currentAnd = candidates[i];
                } else {
                    currentAnd &= candidates[i];
                }
                count++;
            }
        }
        
        // If AND > 0, update maxSize
        if (currentAnd > 0) {
            if (count > maxSize) {
                maxSize = count;
            }
        }
    }
    
    return maxSize;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple JSON array parsing
    int candidates[100];
    int n = 0;
    char* token = strtok(line + 1, ",]"); // Skip '['
    while (token != NULL) {
        candidates[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(candidates, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2^n)

Generate 2^n combinations, each taking O(n) time to compute AND

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for tracking, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler