Largest Combination With Bitwise AND Greater Than Zero

Medium

Google

3 views

Topics:

Bit Manipulation

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. For example:

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.

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 <= 10^5
1 <= candidates[i] <= 10^7

Largest Combination With Bitwise AND Greater Than Zero

Medium

Google

3 views

Topics:

Bit Manipulation

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. For example:

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.

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 <= 10^5
1 <= candidates[i] <= 10^7

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array?
Can the input array be empty or contain null?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?
If no combination has a bitwise AND greater than zero, what should I return?
What is the maximum size of the input array?

Brute Force Solution

Approach

The brute force approach involves checking every possible combination of numbers from the given set. We aim to identify the largest group of numbers that, when combined using a bitwise AND operation, results in a value greater than zero. This means we'll test all subsets and check their AND result.

Here's how the algorithm would work step-by-step:

Consider each number from the set individually as a potential combination.
Now, consider all pairs of numbers, then all groups of three numbers, then all groups of four, and so on until you consider the entire set of numbers as a single combination.
For each combination, perform the bitwise AND operation on all the numbers within that combination.
Check if the result of the bitwise AND operation is greater than zero.
If the result is greater than zero, remember the size (number of elements) of that combination.
After checking all possible combinations, identify the largest size among those combinations whose bitwise AND result was greater than zero.
Report this largest size as the answer.

Code Implementation

def largest_combination_brute_force(numbers):
    max_combination_size = 0
    number_of_numbers = len(numbers)

    # Iterate through all possible combinations using bit manipulation.
    for i in range(1, 2**number_of_numbers):
        current_combination = []

        # Construct the current combination based on the bits set in 'i'.
        for j in range(number_of_numbers):
            if (i >> j) & 1:
                current_combination.append(numbers[j])

        # The base case for the bitwise AND is the first element
        bitwise_and_result = current_combination[0]
        for k in range(1, len(current_combination)):
            bitwise_and_result &= current_combination[k]

        # Check if bitwise AND is greater than zero.
        if bitwise_and_result > 0:

            # Update the max size if current size is larger
            if len(current_combination) > max_combination_size:
                max_combination_size = len(current_combination)

    return max_combination_size

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach iterates through all possible combinations (subsets) of the input array. An array of size n has 2^n possible subsets. For each subset, a bitwise AND operation needs to be performed on all its elements, which takes O(n) time in the worst case (when the subset contains all n elements). Therefore, the overall time complexity involves considering each of the 2^n subsets and performing the AND operation, giving a total complexity approximated by O(n * 2^n). However, since 2^n grows much faster than n, the dominant factor becomes O(2^n) because the cost to perform AND operation on each subset is bounded by the size of the subset which is at most n but still constant to the growth of the number of subsets.

Space Complexity

O(1) – The provided brute force approach iterates through combinations and calculates bitwise AND results. No auxiliary data structures are used to store intermediate combinations or track visited states. Only a constant amount of extra space is required to hold the current combination size and the maximum size found so far, independent of the input array's size, N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The problem asks us to find the largest group of numbers where every number shares at least one common 'on' bit. The key idea is to count how many numbers have each bit 'on' in a specific position, and the largest count is the answer.

Here's how the algorithm would work step-by-step:

Imagine each number as a collection of 'on' and 'off' switches.
Focus on one switch position at a time (like the rightmost switch, then the switch to its left, and so on).
Count how many numbers have that particular switch 'on'.
Repeat the counting process for every switch position.
The largest of these counts represents the biggest group of numbers sharing at least one 'on' switch in the same position.

Code Implementation

def largestCombination(candidates):
    largest_combination_size = 0
    number_of_integers = len(candidates)

    # Iterate through all 32 bits.
    for bit_position in range(32):
        current_combination_size = 0

        # Count integers with the bit set at current bit position.
        for integer_index in range(number_of_integers):
            if (candidates[integer_index] >> bit_position) & 1:
                current_combination_size += 1

        # Keep track of the largest combination size.
        largest_combination_size = max(largest_combination_size, current_combination_size)

    return largest_combination_size

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each number in the input array of size n. Inside the loop, it examines each bit position of the current number. Since the numbers are integers, the number of bit positions is fixed (e.g., 32 for 32-bit integers) and does not depend on the input size n. Therefore, the inner loop's iterations are constant. Thus, the overall time complexity is dominated by the outer loop, which iterates n times. So the time complexity is O(n).

Space Complexity

O(1) – The algorithm iterates through bit positions and counts how many numbers have that bit set. It maintains a count for each bit position but doesn't store the numbers themselves. The number of bit positions is fixed (e.g., 32 bits for integers), so the space required to store the counts is constant, independent of the input size N (the number of numbers). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 as there are no elements to form a combination.
Array containing only zero values	Return 0, as any combination will result in a bitwise AND of 0.
Array containing a single element	Return 1, since the largest combination will just be the element itself.
Array with elements having no common set bits	Return 1 since any single element by itself would be the largest combination.
Large integer values that might cause integer overflow during intermediate calculations.	Use bit manipulation to avoid arithmetic operations which reduces the potential for overflow.
Array with many elements sharing a common bit pattern.	The bit counting approach efficiently determines the largest combination sharing a bit, which is scalable.
Array containing the maximum integer value (e.g., Integer.MAX_VALUE)	The bit counting method correctly handles maximum values as these simply contribute to the respective bit counts.
Array of mixed positive and negative numbers.	Treat negative numbers as their two's complement representation, as bitwise AND is still well-defined and the algorithm counts the set bits.