Jobs

Interviews

Discussions

Largest Combination With Bitwise AND Greater Than Zero

Medium

Asked by:

17 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.

Example 1:

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.

Example 2:

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⁵
1 <= candidates[i] <= 10⁷

Try coding it in LeetCode

Largest Combination With Bitwise AND Greater Than Zero

Medium

Asked by:

17 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.

Example 1:

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.

Example 2:

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⁵
1 <= candidates[i] <= 10⁷

Try coding it in LeetCode

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 are the constraints on the range of the positive integers in the `candidates` array?
Is it possible for the input array `candidates` to be empty?
Are duplicate numbers allowed in the `candidates` array, and if so, how should they be handled in a combination?
If no combination can be found where the bitwise AND is greater than zero, what should be returned?
Does 'combination' imply that the order of elements matters, or is it a subset where order is irrelevant?

Brute Force Solution

Approach

The problem asks us to find the largest possible number that can be formed by taking the bitwise AND of some numbers from a given list, such that the result is greater than zero. The brute force approach systematically checks every possible group of numbers from the list to see if their bitwise AND is positive.

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

First, consider taking just one number from the list and check if its bitwise AND with itself is greater than zero. Keep track of the largest such number.
Next, try taking every possible pair of numbers from the list. For each pair, calculate their bitwise AND. If this result is greater than zero, compare it with the largest positive result found so far and update if it's bigger.
Then, consider every possible group of three numbers from the list. Calculate the bitwise AND of each group. If the result is positive, compare it with the current largest positive result and update if necessary.
Continue this process by trying every possible group of four numbers, then five, and so on, up to taking all the numbers in the list together.
For each group, you calculate the bitwise AND of all the numbers in that group. If the final result of this bitwise AND operation is greater than zero, you compare this result with the largest positive bitwise AND result you've encountered so far.
If the current group's bitwise AND is larger than the largest one you've recorded, you update your record to this new larger value.
After you have checked every single possible group of numbers from the original list, the largest positive bitwise AND result you have recorded is your answer.

Code Implementation

import itertoolsdef largest_combination_bitwise_and_greater_than_zero(list_of_numbers):    largest_positive_bitwise_and_result = 0    # The problem requires checking every possible combination of numbers,    # starting from individual numbers up to the entire list.    for group_size in range(1, len(list_of_numbers) + 1):        # Iterate through all possible combinations for the current group size.        for current_combination in itertools.combinations(list_of_numbers, group_size):            current_bitwise_and_result = current_combination[0]            # Perform bitwise AND operation for all numbers in the current combination.            for number_in_combination in current_combination[1:]:                current_bitwise_and_result &= number_in_combination            # Update the largest result if the current combination's AND is positive and larger.            if current_bitwise_and_result > 0 and current_bitwise_and_result > largest_positive_bitwise_and_result:                largest_positive_bitwise_and_result = current_bitwise_and_result    # Return the maximum positive bitwise AND found across all combinations.    return largest_positive_bitwise_and_result

Big(O) Analysis

Time Complexity

O(2^n * n) – The described approach involves checking every possible combination (subset) of numbers from the input list. If the list has n numbers, there are 2^n possible subsets. For each subset, we perform a bitwise AND operation. The bitwise AND operation on k numbers takes O(k) time. In the worst case, k can be up to n. Therefore, the total time complexity is the sum of the cost of processing each subset. Summing O(k) for all 2^n subsets, where k can go up to n, leads to a total time complexity of O(2^n * n).

Space Complexity

O(1) – The provided plain English explanation describes an iterative process of checking combinations. It mentions keeping track of the 'largest such number' or 'largest positive result found so far', which implies the use of a single variable to store this maximum value. No additional data structures like auxiliary arrays, hash maps, or recursion stacks are described as being created or utilized, meaning the space complexity is constant and independent of the input size N.

Optimal Solution

Approach

The problem asks us to find the largest number that can be formed by choosing a subset of the given numbers such that their bitwise AND operation results in a value greater than zero. The key insight is that if a bit is set in the final result, it must be set in all the numbers contributing to that result. Therefore, we can count how many numbers have each specific bit position set.

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

Examine each bit position, starting from the least significant one up to the most significant one, for all the given numbers.
For each bit position, count how many of the given numbers have that specific bit turned on (i.e., a '1' at that position).
Keep track of the highest count found so far.
The bit position that has the highest count of numbers with that bit set is the most important bit for forming a large number.
If multiple bit positions have the same highest count, any one of them can be chosen. However, to maximize the resulting number, it's generally better to pick the bit position that is further to the left (representing a larger value).
The largest possible combination will be formed by selecting all the numbers that have the most frequent bit set. The value of this combination is not the sum, but rather the bitwise AND of these selected numbers, which is guaranteed to be greater than zero if the count is at least 1.
The answer is the highest count found for any single bit position, as this represents the largest group of numbers that can share at least one common '1' bit, thus yielding a bitwise AND greater than zero.

Code Implementation

def largest_combination(candidates):
    maximum_bit_position = 30 # Assuming numbers fit within 32-bit integers
    maximum_count_for_any_bit = 0

    # Iterate through each possible bit position to check its frequency.
    for current_bit_index in range(maximum_bit_position + 1):
        current_bit_count = 0
        # Count how many numbers have the current bit set.
        for number_in_list in candidates:
            if (number_in_list >> current_bit_index) & 1:
                current_bit_count += 1
        
        # Update the maximum count if the current bit position has more numbers with it set.
        maximum_count_for_any_bit = max(maximum_count_for_any_bit, current_bit_count)

    # The largest combination is the maximum count of numbers sharing a common set bit.
    return maximum_count_for_any_bit

Big(O) Analysis

Time Complexity

O(n*k) – The solution iterates through each bit position up to a maximum of k bits (typically 32 for standard integers). For each bit, it then iterates through all n numbers in the input array to count how many have that bit set. This results in a total of n * k operations. Since k is a constant for a given integer size, the time complexity is effectively linear with respect to the number of input elements, n.

Space Complexity

O(1) – The solution iterates through each bit position. It uses a constant number of variables to store the count for the current bit and the maximum count found so far. The maximum number of bits to check is fixed (e.g., 32 for standard integers), regardless of the input size N. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Input array is null or empty	The solution should return 0 as no combination can be formed.
Input array contains only one element	If the single element is positive, the largest combination size is 1; otherwise, it's 0.
All numbers in the input array are identical	The solution should correctly identify the bitwise AND of all identical numbers and return the array size if it's greater than zero, otherwise 0.
Input contains zeros	Zeros will result in a bitwise AND of 0, so they should effectively be ignored for combinations where the AND must be positive.
Input contains negative numbers	The problem statement specifies positive integers, so negative numbers are not expected; if present, they should be handled by filtering them out or raising an error.
No combination results in a bitwise AND greater than zero	The solution should correctly return 0 in this scenario.
Large number of bits set in common across many numbers	The algorithm's efficiency relies on bit manipulation, which is generally constant time per bit, so it should scale well with the number of bits but can be impacted by the number of candidates.
Maximum integer values in the input array	Ensure that bitwise operations do not lead to integer overflow if the language has fixed-size integers and extremely large inputs are possible.

Input array is null or empty

How to Handle:

The solution should return 0 as no combination can be formed.

Input array contains only one element

How to Handle:

If the single element is positive, the largest combination size is 1; otherwise, it's 0.

All numbers in the input array are identical

How to Handle:

The solution should correctly identify the bitwise AND of all identical numbers and return the array size if it's greater than zero, otherwise 0.

Input contains zeros

How to Handle:

Zeros will result in a bitwise AND of 0, so they should effectively be ignored for combinations where the AND must be positive.

Input contains negative numbers

How to Handle:

The problem statement specifies positive integers, so negative numbers are not expected; if present, they should be handled by filtering them out or raising an error.

No combination results in a bitwise AND greater than zero

How to Handle:

The solution should correctly return 0 in this scenario.

Large number of bits set in common across many numbers

How to Handle:

The algorithm's efficiency relies on bit manipulation, which is generally constant time per bit, so it should scale well with the number of bits but can be impacted by the number of candidates.

Maximum integer values in the input array

How to Handle:

Ensure that bitwise operations do not lead to integer overflow if the language has fixed-size integers and extremely large inputs are possible.

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 are the constraints on the range of the positive integers in the `candidates` array?
Is it possible for the input array `candidates` to be empty?
Are duplicate numbers allowed in the `candidates` array, and if so, how should they be handled in a combination?
If no combination can be found where the bitwise AND is greater than zero, what should be returned?
Does 'combination' imply that the order of elements matters, or is it a subset where order is irrelevant?

Brute Force Solution

Approach

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

First, consider taking just one number from the list and check if its bitwise AND with itself is greater than zero. Keep track of the largest such number.
Next, try taking every possible pair of numbers from the list. For each pair, calculate their bitwise AND. If this result is greater than zero, compare it with the largest positive result found so far and update if it's bigger.
Then, consider every possible group of three numbers from the list. Calculate the bitwise AND of each group. If the result is positive, compare it with the current largest positive result and update if necessary.
Continue this process by trying every possible group of four numbers, then five, and so on, up to taking all the numbers in the list together.
For each group, you calculate the bitwise AND of all the numbers in that group. If the final result of this bitwise AND operation is greater than zero, you compare this result with the largest positive bitwise AND result you've encountered so far.
If the current group's bitwise AND is larger than the largest one you've recorded, you update your record to this new larger value.
After you have checked every single possible group of numbers from the original list, the largest positive bitwise AND result you have recorded is your answer.

Code Implementation

import itertoolsdef largest_combination_bitwise_and_greater_than_zero(list_of_numbers):    largest_positive_bitwise_and_result = 0    # The problem requires checking every possible combination of numbers,    # starting from individual numbers up to the entire list.    for group_size in range(1, len(list_of_numbers) + 1):        # Iterate through all possible combinations for the current group size.        for current_combination in itertools.combinations(list_of_numbers, group_size):            current_bitwise_and_result = current_combination[0]            # Perform bitwise AND operation for all numbers in the current combination.            for number_in_combination in current_combination[1:]:                current_bitwise_and_result &= number_in_combination            # Update the largest result if the current combination's AND is positive and larger.            if current_bitwise_and_result > 0 and current_bitwise_and_result > largest_positive_bitwise_and_result:                largest_positive_bitwise_and_result = current_bitwise_and_result    # Return the maximum positive bitwise AND found across all combinations.    return largest_positive_bitwise_and_result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Examine each bit position, starting from the least significant one up to the most significant one, for all the given numbers.
For each bit position, count how many of the given numbers have that specific bit turned on (i.e., a '1' at that position).
Keep track of the highest count found so far.
The bit position that has the highest count of numbers with that bit set is the most important bit for forming a large number.
If multiple bit positions have the same highest count, any one of them can be chosen. However, to maximize the resulting number, it's generally better to pick the bit position that is further to the left (representing a larger value).
The largest possible combination will be formed by selecting all the numbers that have the most frequent bit set. The value of this combination is not the sum, but rather the bitwise AND of these selected numbers, which is guaranteed to be greater than zero if the count is at least 1.
The answer is the highest count found for any single bit position, as this represents the largest group of numbers that can share at least one common '1' bit, thus yielding a bitwise AND greater than zero.

Code Implementation

def largest_combination(candidates):
    maximum_bit_position = 30 # Assuming numbers fit within 32-bit integers
    maximum_count_for_any_bit = 0

    # Iterate through each possible bit position to check its frequency.
    for current_bit_index in range(maximum_bit_position + 1):
        current_bit_count = 0
        # Count how many numbers have the current bit set.
        for number_in_list in candidates:
            if (number_in_list >> current_bit_index) & 1:
                current_bit_count += 1
        
        # Update the maximum count if the current bit position has more numbers with it set.
        maximum_count_for_any_bit = max(maximum_count_for_any_bit, current_bit_count)

    # The largest combination is the maximum count of numbers sharing a common set bit.
    return maximum_count_for_any_bit

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array is null or empty	The solution should return 0 as no combination can be formed.
Input array contains only one element	If the single element is positive, the largest combination size is 1; otherwise, it's 0.
All numbers in the input array are identical	The solution should correctly identify the bitwise AND of all identical numbers and return the array size if it's greater than zero, otherwise 0.
Input contains zeros	Zeros will result in a bitwise AND of 0, so they should effectively be ignored for combinations where the AND must be positive.
Input contains negative numbers	The problem statement specifies positive integers, so negative numbers are not expected; if present, they should be handled by filtering them out or raising an error.
No combination results in a bitwise AND greater than zero	The solution should correctly return 0 in this scenario.
Large number of bits set in common across many numbers	The algorithm's efficiency relies on bit manipulation, which is generally constant time per bit, so it should scale well with the number of bits but can be impacted by the number of candidates.
Maximum integer values in the input array	Ensure that bitwise operations do not lead to integer overflow if the language has fixed-size integers and extremely large inputs are possible.

Input array is null or empty

How to Handle:

The solution should return 0 as no combination can be formed.

Input array contains only one element

How to Handle:

If the single element is positive, the largest combination size is 1; otherwise, it's 0.

All numbers in the input array are identical

How to Handle:

The solution should correctly identify the bitwise AND of all identical numbers and return the array size if it's greater than zero, otherwise 0.

Input contains zeros

How to Handle:

Zeros will result in a bitwise AND of 0, so they should effectively be ignored for combinations where the AND must be positive.

Input contains negative numbers

How to Handle:

The problem statement specifies positive integers, so negative numbers are not expected; if present, they should be handled by filtering them out or raising an error.

No combination results in a bitwise AND greater than zero

How to Handle:

The solution should correctly return 0 in this scenario.

Large number of bits set in common across many numbers

How to Handle:

The algorithm's efficiency relies on bit manipulation, which is generally constant time per bit, so it should scale well with the number of bits but can be impacted by the number of candidates.

Maximum integer values in the input array

How to Handle:

Ensure that bitwise operations do not lead to integer overflow if the language has fixed-size integers and extremely large inputs are possible.