Abstract / Summary

Find the largest number by setting bits from highest to lowest so their bitwise AND is not zero.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 81% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• Counting
• Hash Table

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method largestCombination that receives a list of non-negative integers (candidates) and returns the size of the largest subset of these numbers that share at least one common set bit. The algorithm works by counting how many numbers have each bit position set, then selecting the maximum count across all bit positions.

Key Steps

Defining the Bit Range

maxbits = 24  # 2^24 > 10^7
bits    = [0] * maxbits

The method assumes that the input numbers never exceed (10^7). Because (2^{24}) is larger than that bound, a fixed array of length 24 is sufficient to hold the count for each possible bit position. This eliminates the need for dynamic resizing and keeps the memory footprint predictable.

Iterating Over the Input Numbers

for n in candidates:
    mask = 1
    for i in range(maxbits):
        if n & mask:          # count bit
            bits[i] += 1

        if n < mask:         # for performance only
            break

        mask *= 2

For each integer n the inner loop walks through the bit positions from least significant to most significant. The expression n & mask tests whether the current bit is set; when true the corresponding counter in bits is incremented.

The condition if n < mask: break stops the inner loop as soon as the mask exceeds the value of n. Since any higher bits must be zero, the loop can safely terminate early, avoiding unnecessary iterations for small numbers.

Selecting the Largest Count

return max(bits)

After all numbers have been processed, the method returns the highest value stored in the bits array, which represents the largest number of candidates sharing a particular set bit.

Edge Cases Handled

When the input list candidates is empty, the outer loop never executes and the bits array remains filled with zeros. The final max(bits) call therefore returns 0, correctly indicating that no combination exists.

If a candidate value is exactly zero, the inner loop immediately encounters n < mask on the first iteration (mask == 1) and breaks without incrementing any counters, ensuring that zero does not contribute to any bit count.

Numbers that are larger than the assumed bound (greater than (2^{24}-1)) would still be processed, but bits beyond index 23 are ignored because the loop limits itself to maxbits. This behavior effectively treats any higher bits as irrelevant for the result.

Performance Optimizations

The early-break condition if n < mask: break reduces the number of inner-loop iterations for small numbers, preventing the algorithm from scanning all 24 bit positions when it is unnecessary.

Using a pre-allocated list bits of fixed size avoids repeated memory allocation during counting.

The mask is updated by multiplication (mask *= 2) rather than using a left-shift operation; both are O(1) but multiplication keeps the code straightforward and works reliably for the limited range of values.

By limiting the bit range to 24 based on the problem’s numeric constraints, the algorithm avoids the overhead of handling arbitrarily large integers, keeping the per-element work bounded and predictable.

Imagine a group of numbers waiting to be picked for a team. To decide which numbers work best together, think of them as being made up of little glowing light bulbs. Each number has a different pattern of bulbs turned on and off. The goal is to find the biggest group of numbers that share the same glowing bulb in the exact same spot.

First, prepare twenty-four small boxes to act as counters, one for each position where a bulb could be. Start with every box empty, holding the number zero. Then, look at each number in the list one by one. For every number, check each bulb position. If a bulb is shining at that position, put a little mark in the matching box. By moving through the numbers and checking their bulbs, the boxes keep track of how many numbers have a light on in that specific spot. Once every number has been checked, look at all the boxes to see which one holds the highest count. That count tells how many numbers can be joined together while all sharing a light in the same spot.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python			TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++		Java	Python		Go	TS
	Progiez	C++		Java	Python
github	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	Shamik07					Dart
	varunu28			Java
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
varunu28	Java
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality