Maximum Number That Makes Result of Bitwise AND Zero

Medium

Asked by:

7 views

Topics:

Bit Manipulation

You are given an integer array nums.

You need to choose a subset of nums such that the bitwise AND of all numbers in the subset is equal to 0.

Return the maximum possible sum of the elements in the chosen subset.

Note:

A subset can be empty. In that case, the bitwise AND of the subset is considered to be 2³⁰ - 1. And an empty subset has a sum of 0.

Example 1:

Input: nums = [5,1,3]
Output: 8
Explanation:
We can choose the subset {5, 3} such that the bitwise AND of all numbers in the subset is equal to 0. The sum of this subset is 5 + 3 = 8, which is the maximum possible sum.

Example 2:

Input: nums = [7,3,2,1,5,8]
Output: 23
Explanation:
We can choose the subset {7, 3, 5, 8} such that the bitwise AND of all numbers in the subset is equal to 0. The sum of this subset is 7 + 3 + 5 + 8 = 23, which is the maximum possible sum.

Example 3:

Input: nums = [8,13,8,10,20]
Output: 41
Explanation:
We can choose the subset {13, 8, 10, 20} such that the bitwise AND of all numbers in the subset is equal to 0. The sum of this subset is 13 + 8 + 10 + 20 = 41, which is the maximum possible sum.

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

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 is the maximum possible value for elements within the `nums` array?
Can the input array `nums` be empty?
Are all the numbers in `nums` non-negative integers, as the problem states?
If multiple integers `x` satisfy the condition, do I need to return the absolute maximum, or can I return any one of them?
Can you provide an example of an edge case where the answer might not be immediately obvious?

Brute Force Solution

Approach

The goal is to find the largest number that, when combined with every number in a given set using a bitwise AND operation, results in zero. The brute force approach involves checking every possible number within a plausible range to see if it satisfies the condition.

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

First, consider the range of possible numbers we need to check. Since we are looking for the largest number, we need to know how big the numbers in the initial set are.
Start with the largest number that could possibly work. A good starting point might be one less than a power of two that is greater than the largest number in the given set.
Take the starting number and perform a bitwise AND operation with each number in the set.
If the result of the bitwise AND with every number in the set is zero, then we've found a valid solution. We should record this number.
If not, decrease the number by one and repeat the bitwise AND operation with every number in the set.
Continue decreasing the number and checking until a valid solution is found or until we reach the lower bound of our search range, such as zero.
If at any point we find a number that works, this number is a possible candidate for our answer; Since we started from the largest possible number, the first number we find will be the largest number that makes the result zero.

Code Implementation

def find_maximum_subset_sum(numbers):
    maximum_sum = 0
    number_of_numbers = len(numbers)

    # Iterate through all possible subsets of the input list.
    for i in range(1, 1 << number_of_numbers):
        current_subset = []

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

        # Calculate bitwise AND of the current subset
        bitwise_and_result = current_subset[0]

        for k in range(1, len(current_subset)):
            bitwise_and_result &= current_subset[k]

        # Check if the bitwise AND result is zero.
        if bitwise_and_result == 0:

            #If bitwise AND is zero, calculate sum.
            current_sum = sum(current_subset)

            #Update maximum sum with the current sum if larger.
            if current_sum > maximum_sum:
                maximum_sum = current_sum

    return maximum_sum

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates downwards from a maximum possible value m (dependent on the largest number in the input set) until it finds a number that satisfies the condition. For each candidate number, it performs a bitwise AND operation with each of the n numbers in the input set. In the worst case, it might have to check a large number of candidate numbers, up to m, before finding a solution or reaching zero. Thus, the time complexity is O(m*n), where m represents the maximum possible value checked and n is the size of the input set.

Space Complexity

O(1) – The described algorithm iterates through potential numbers and performs bitwise AND operations. It doesn't explicitly create any auxiliary data structures like lists, arrays, or hash maps to store intermediate results. The space used is limited to storing a few variables, such as the current number being tested and potentially a variable to store the largest valid solution found so far, all of which take constant space, irrespective of the input set size N. Thus, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find the largest number less than a given input, where that number, when combined with every number in a given set using a bitwise operation, results in zero. Instead of checking every possible number, we focus on building the result from the 'opposite' bits found in the set of numbers.

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

Examine all the numbers in the provided set to see which bit positions have a '1' in at least one of the numbers.
Consider each of those bit positions that have a '1' at least once.
Construct a new number that has '0' at those positions and '1' everywhere else, effectively inverting the bits we found.
Take this new number. If it's smaller or the same as the initial input number, then we've found our answer. If not...
Repeat the steps, but consider only numbers smaller than the original number

Code Implementation

def maximum_number_that_makes_result_of_bitwise_and_zero(numbers):
    maximum_possible_number = max(numbers)
    number_of_inputs = len(numbers)
    total_integers = maximum_possible_number + 1
    count = 0

    for mask in range(1, 1 << number_of_inputs):
        current_intersection = total_integers - 1
        subset_size = 0
        for j in range(number_of_inputs):
            if (mask >> j) & 1:
                #Determine intersection based on current bit
                current_intersection &= ~numbers[j]
                subset_size += 1

        if subset_size % 2 == 1:
            # Inclusion-exclusion principle: Add for odd subset sizes
            count += current_intersection + 1

        else:
            # Inclusion-exclusion principle: Subtract for even subset sizes
            count -= current_intersection + 1

    # The final result is derived by subtracting the calculated count.
    return total_integers - count -1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of numbers once to identify the bit positions that have at least one '1'. The number of iterations is directly proportional to the number of elements (n) in the input array. After this initial scan, constructing the result involves a fixed number of bitwise operations and comparisons which do not depend on the input size. Therefore, the dominant factor in the time complexity is the initial linear scan of the input array, leading to a time complexity of O(n).

Space Complexity

O(1) – The provided solution primarily manipulates bits and calculates a resulting number. It identifies bit positions with a '1' present in the input set, but the storage required for these bit positions is bounded by the bit length of the input numbers, which is typically constant (e.g., 32 or 64 bits). Therefore, the auxiliary space used to store which bit positions have a '1' is constant, independent of the number of input numbers (N). Thus, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return the maximum possible integer value since the condition is trivially satisfied for any x.
Array with a single element	Return the bitwise complement of the single element, ensuring it's within the integer range.
All elements in the array are zero	Return the maximum possible integer value as the bitwise AND will always be zero.
Array contains only the maximum integer value	Return zero, as any other number's bitwise AND with the maximum integer will not be zero.
Large input array (performance considerations)	Iterate through the array to calculate the bitwise OR of all elements, then return the complement.
Integer overflow when calculating the complement	Use a bitmask to ensure the result remains within the valid integer range.
Array with mixed small and large numbers	The bitwise OR operation will handle the mixture of small and large numbers correctly when computing the complement.
No valid solution smaller than MAX_INT (should always be possible since x=0 is a valid result)	The solution ensures that at least x=0 is a viable option, and aims for the largest possible that satisfies the conditions.

Null or empty input array

How to Handle:

Return the maximum possible integer value since the condition is trivially satisfied for any x.

Array with a single element

How to Handle:

Return the bitwise complement of the single element, ensuring it's within the integer range.

All elements in the array are zero

How to Handle:

Return the maximum possible integer value as the bitwise AND will always be zero.

Array contains only the maximum integer value

How to Handle:

Return zero, as any other number's bitwise AND with the maximum integer will not be zero.

Large input array (performance considerations)

How to Handle:

Iterate through the array to calculate the bitwise OR of all elements, then return the complement.

Integer overflow when calculating the complement

How to Handle:

Use a bitmask to ensure the result remains within the valid integer range.

Array with mixed small and large numbers

How to Handle:

The bitwise OR operation will handle the mixture of small and large numbers correctly when computing the complement.

No valid solution smaller than MAX_INT (should always be possible since x=0 is a valid result)

How to Handle:

The solution ensures that at least x=0 is a viable option, and aims for the largest possible that satisfies the conditions.