What is the brute force approach and complexity for Largest Combination With Bitwise AND Greater Than Zero?

Try all 2^N groups, AND each one, keep the biggest with AND > 0 with time complexity O(N · 2^N) and space complexity O(1).

What is the optimal approach and complexity for Largest Combination With Bitwise AND Greater Than Zero?

For each bit, count the candidates that have it; the answer is the biggest count with optimal time complexity O(24 · N) and space complexity O(1).

How do you identify the pattern for Largest Combination With Bitwise AND Greater Than Zero?

Look for key signals in the prompt: "bitwise AND of the combination greater than 0" indicates The AND is above 0 only when one bit is shared by every member, so the test is per bit.; "size of the largest combination" indicates Count how many numbers share each bit. The largest count is the answer.; "candidates up to 10^7" indicates Only 24 bits can be set, so one pass per bit is cheap. Trying every group is not..

Largest Combination With Bitwise AND Greater Than Zero

Medium·LeetCode #2275 Pro OnlySlight Variation

LeetCode

Problem Statement

The AND of a group of numbers is the bitwise AND of all of them. For example, 1 & 5 & 3 = 1, and a group with one number has an AND equal to that number.

You are given an array candidates of positive integers. Pick any group of them, using each candidate at most once, and compute the AND of the group. Return the size of the largest group whose AND is greater than 0.

Input

An array candidates of positive integers.

Output

The size of the largest group of candidates whose bitwise AND is greater than 0.

Example 1

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

Output: 4

The group [16, 17, 62, 24] has AND 16 & 17 & 62 & 24 = 16 > 0, so its size 4 counts. A group of 5 or more never has AND above 0. The group [62, 12, 24, 14] also works, with AND 8.

Example 2

Input: candidates = [8, 8]

Output: 2

8 & 8 = 8 > 0, so the whole array is a valid group of size 2.

Constraints

• 1 ≤ candidates.length ≤ 10^5
• 1 ≤ candidates[i] ≤ 10^7

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“bitwise AND of the combination greater than 0”

→ The AND is above 0 only when one bit is shared by every member, so the test is per bit.

“size of the largest combination”

→ Count how many numbers share each bit. The largest count is the answer.

“candidates up to 10^7”

→ Only 24 bits can be set, so one pass per bit is cheap. Trying every group is not.

Approach Complexity Ladder

Brute Force — try every groupO(N · 2^N)O(1)

Try all 2^N groups, AND each one, keep the biggest with AND > 0

Optimal — count each bitO(24 · N)O(1)

For each bit, count the candidates that have it; the answer is the biggest count

Brute Force Intuition

Every group is a subset of the array. For each non-empty group, compute its AND. If the AND is above 0 and the group is bigger than the best so far, keep its size.

Recognition rule for this sub-pattern:

Look for the common prefix of bits, or use prefix XOR like prefix sums.

Remember this · Bit Manipulation

Trigger

"Every element appears twice except…", power of two, counting set bits, subsets as bitmasks, O(1) space tricks.

Think

What happens to this problem if I look at each bit separately?

Key question

Which bit operation (XOR, AND, OR, shift) cancels or isolates what I need?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Bit Manipulation translate into production architectures and low-level memory mechanics.

LLD Architecture