We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Combination With Bitwise AND Greater Than Zero

Number: 2356

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft, Adobe

Problem Description

Given an array of positive integers, find the size of the largest combination (i.e. subsequence) from the array such that the bitwise AND of all the numbers in that combination is greater than zero.

Key Insights

  • The bitwise AND of a set of numbers is greater than zero if and only if there exists at least one bit position that is set (i.e. 1) in every number of the combination.
  • Instead of checking every combination, realize that if you select numbers sharing a common bit, then their bitwise AND will have that bit set and be greater than zero.
  • Count how many numbers in the array have each particular bit set. The answer is the maximum count among all bit positions.
  • The maximum candidate value is up to 10^7, so only a limited number of bits (about 25-32) need to be considered.

Space and Time Complexity

Time Complexity: O(n * B) where n is the number of elements and B is the number of bits we check (B is constant ~ 32). Space Complexity: O(1), as we only use a fixed-size counter for bits.

Solution

To solve this problem, we use the following algorithm:

  1. Initialize an array (or dictionary) to count occurrences for each bit position.
  2. Loop through each number in the candidates array.
  3. For each number, for every bit position (from 0 to 31), check if that bit is set. If yes, increment the count for that bit.
  4. The largest combination that can produce a bitwise AND greater than zero is the maximum count found among all bit positions. This is because each such count represents the number of candidates that share that specific bit.
  5. Return the maximum count.

Key data structure: a fixed size array (or simple integer counts for each bit) to tally counts, ensuring the solution is efficient.

Code Solutions

# Python implementation
def largestCombination(candidates):
    # Initialize counts for 32 bits (sufficient for values <= 10^7)
    bit_count = [0] * 32
    # Iterate over each candidate number
    for num in candidates:
        # Check each bit position from 0 to 31
        for i in range(32):
            # If bit i is set in num, increment count for that bit
            if num & (1 << i):
                bit_count[i] += 1
    # The result is the maximum count among all bits
    return max(bit_count)

# Example usage:
# candidates = [16,17,71,62,12,24,14]
# print(largestCombination(candidates))  # Output: 4
← Back to All Questions