Jobs

Interviews

Discussions

Maximum OR

Medium

Asked by:

21 views

Topics:

ArraysGreedy AlgorithmsBit Manipulation

You are given a 0-indexed integer array nums of length n and an integer k. In an operation, you can choose an element and multiply it by 2.

Return the maximum possible value of nums[0] | nums[1] | ... | nums[n - 1] that can be obtained after applying the operation on nums at most k times.

Note that a | b denotes the bitwise or between two integers a and b.

Example 1:

Input: nums = [12,9], k = 1
Output: 30
Explanation: If we apply the operation to index 1, our new array nums will be equal to [12,18]. Thus, we return the bitwise or of 12 and 18, which is 30.

Example 2:

Input: nums = [8,1,2], k = 2
Output: 35
Explanation: If we apply the operation twice on index 0, we yield a new array of [32,1,2]. Thus, we return 32|1|2 = 35.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 15

Try coding it in LeetCode

Maximum OR

Medium

Asked by:

21 views

Topics:

ArraysGreedy AlgorithmsBit Manipulation

You are given a 0-indexed integer array nums of length n and an integer k. In an operation, you can choose an element and multiply it by 2.

Return the maximum possible value of nums[0] | nums[1] | ... | nums[n - 1] that can be obtained after applying the operation on nums at most k times.

Note that a | b denotes the bitwise or between two integers a and b.

Example 1:

Input: nums = [12,9], k = 1
Output: 30
Explanation: If we apply the operation to index 1, our new array nums will be equal to [12,18]. Thus, we return the bitwise or of 12 and 18, which is 30.

Example 2:

Input: nums = [8,1,2], k = 2
Output: 35
Explanation: If we apply the operation twice on index 0, we yield a new array of [32,1,2]. Thus, we return 32|1|2 = 35.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 15

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 upper bounds for the values in the `nums` array and the value of `k`?
Can the input array `nums` be empty or null?
Is there any specific order in which I should apply the multiplication operations to maximize the bitwise OR?
If performing all `k` operations doesn't improve the bitwise OR, should I still perform all `k` operations or stop early?
Are all numbers in the input array guaranteed to be non-negative integers?

Brute Force Solution

Approach

The brute force method for finding the maximum OR value involves trying every possible combination. We consider all possible sub-groups of the given numbers. Then, we calculate the OR result for each of these sub-groups and determine the highest value.

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

First, we consider the simplest cases: each number on its own is a possible sub-group.
Then, we start building larger sub-groups by combining pairs of numbers.
Next, we try combining three numbers at a time, and so on, until we've considered a sub-group that includes all the numbers.
For each sub-group we create, we perform the OR operation on all the numbers within it.
We then compare the result of each OR operation with the current highest value we've found so far.
If the current OR result is higher, we replace the stored highest value with this new one.
After trying every possible sub-group and calculating their OR result, the final stored highest value will be the maximum OR that can be obtained.

Code Implementation

def maximum_or_brute_force(numbers):
    maximum_or_value = 0
    number_of_numbers = len(numbers)

    # Iterate through all possible subsets of the numbers
    for i in range(1, 1 << number_of_numbers):
        current_or_value = 0
        
        # Construct the subset and compute the OR
        for j in range(number_of_numbers):
            # Check if j-th element is present in the subset
            if (i >> j) & 1:
                current_or_value |= numbers[j]

        # Update the maximum OR value if necessary
        if current_or_value > maximum_or_value:
            maximum_or_value = current_or_value

    return maximum_or_value

Big(O) Analysis

Time Complexity

O(2^n) – The provided brute force approach considers all possible sub-groups of the input array. For an array of size n, there are 2^n possible sub-groups (each element can either be present or absent in a sub-group). Calculating the OR operation for each sub-group takes O(n) time in the worst case. Therefore, the overall time complexity is O(n * 2^n). However, the number of sub-groups dominates the linear cost of calculating OR within each, so the time complexity is O(2^n).

Space Complexity

O(1) – The brute force method, as described, doesn't explicitly use any auxiliary data structures like lists or hash maps. It primarily iterates through combinations of numbers and calculates the OR of subgroups. The only extra space used would be for variables to store the current OR result and the maximum OR value found so far, both of which occupy constant space, independent of the input size N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to make the 'OR' result as large as possible by strategically shifting a number. We achieve this by figuring out how many bits we need to shift and then making sure the bits from another number are placed in the most impactful positions of the first number.

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

First, figure out how many bits you can shift the first number to the left. This depends on a given limit.
After determining the allowable shift, create a 'mask'. This mask lets us grab the most significant bits from the second number. Think of the mask as a way to focus on the largest, most influential bits.
Use the mask to isolate the key bits from the second number. The more bits we can pull from the second number the better the OR result will be.
Shift the first number and OR it with the masked bits from the second number. This combines the two numbers to make the overall OR result as large as possible.
Return the final result. This represents the largest possible 'OR' value we can create by shifting and combining the two initial numbers.

Code Implementation

def maximum_or(number1, number2, shift_limit):
    # Determine how much we're allowed to shift number1
    allowable_shift = min(shift_limit, 32) 

    # Creates a mask to extract the significant bits from number2
    mask_for_significant_bits = (1 << allowable_shift) - 1

    # Applies the mask to isolate the key bits of number2
    significant_bits_from_number2 = number2 & mask_for_significant_bits

    # Shifts number1 to the left and combines it with the masked bits from number2
    shifted_number1 = number1 << allowable_shift
    final_result = shifted_number1 | significant_bits_from_number2

    return final_result

Big(O) Analysis

Time Complexity

O(1) – The algorithm involves a fixed number of bitwise operations, shifts, and masking operations. The number of bits to shift is determined by a given constant limit. These operations take a constant amount of time regardless of the input numbers. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The algorithm described operates primarily on the input numbers directly and calculates a shift value. It uses a mask to isolate bits, but the mask itself and any temporary variables used for shifting and bitwise operations consume a constant amount of space, irrespective of the size of the input numbers. Therefore, the auxiliary space complexity is constant. No additional data structures that scale with the input are created.

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0 since no OR operation can be performed on an empty array.
k is 0 (no operations allowed)	Return the initial OR of the input array without any modifications.
Array contains only zero values.	The maximum OR value will always be 0 regardless of k, so return 0.
k is very large (larger than the array size * maximum bits needed to represent an element).	Consider each number multiplied by the largest possible power of 2 until k runs out or its representation reaches the upper bound of the datatype.
Integer overflow when multiplying a number by 2.	Use appropriate data types (e.g., long) to prevent integer overflow during multiplication.
Array contains very large numbers close to the maximum integer value.	Pay attention to how many times a number close to MAX_INT can be multiplied before overflow happens and adjust k accordingly.
All numbers are identical.	Multiply the first number nums[0] by 2 k times, then OR with all other nums[i] to obtain the maximum OR value.
k is large enough to potentially shift all the numbers such that the most significant bit of the resulting OR is set by the most significant bit of the largest number in the input array	The greedy approach should handle this automatically by focusing operations on the number contributing the most to the final OR result.

Empty input array (nums is null or has length 0)

How to Handle:

Return 0 since no OR operation can be performed on an empty array.

k is 0 (no operations allowed)

How to Handle:

Return the initial OR of the input array without any modifications.

Array contains only zero values.

How to Handle:

The maximum OR value will always be 0 regardless of k, so return 0.

k is very large (larger than the array size * maximum bits needed to represent an element).

How to Handle:

Consider each number multiplied by the largest possible power of 2 until k runs out or its representation reaches the upper bound of the datatype.

Integer overflow when multiplying a number by 2.

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during multiplication.

Array contains very large numbers close to the maximum integer value.

How to Handle:

Pay attention to how many times a number close to MAX_INT can be multiplied before overflow happens and adjust k accordingly.

All numbers are identical.

How to Handle:

Multiply the first number nums[0] by 2 k times, then OR with all other nums[i] to obtain the maximum OR value.

k is large enough to potentially shift all the numbers such that the most significant bit of the resulting OR is set by the most significant bit of the largest number in the input array

How to Handle:

The greedy approach should handle this automatically by focusing operations on the number contributing the most to the final OR result.

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 upper bounds for the values in the `nums` array and the value of `k`?
Can the input array `nums` be empty or null?
Is there any specific order in which I should apply the multiplication operations to maximize the bitwise OR?
If performing all `k` operations doesn't improve the bitwise OR, should I still perform all `k` operations or stop early?
Are all numbers in the input array guaranteed to be non-negative integers?

Brute Force Solution

Approach

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

First, we consider the simplest cases: each number on its own is a possible sub-group.
Then, we start building larger sub-groups by combining pairs of numbers.
Next, we try combining three numbers at a time, and so on, until we've considered a sub-group that includes all the numbers.
For each sub-group we create, we perform the OR operation on all the numbers within it.
We then compare the result of each OR operation with the current highest value we've found so far.
If the current OR result is higher, we replace the stored highest value with this new one.
After trying every possible sub-group and calculating their OR result, the final stored highest value will be the maximum OR that can be obtained.

Code Implementation

def maximum_or_brute_force(numbers):
    maximum_or_value = 0
    number_of_numbers = len(numbers)

    # Iterate through all possible subsets of the numbers
    for i in range(1, 1 << number_of_numbers):
        current_or_value = 0
        
        # Construct the subset and compute the OR
        for j in range(number_of_numbers):
            # Check if j-th element is present in the subset
            if (i >> j) & 1:
                current_or_value |= numbers[j]

        # Update the maximum OR value if necessary
        if current_or_value > maximum_or_value:
            maximum_or_value = current_or_value

    return maximum_or_value

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, figure out how many bits you can shift the first number to the left. This depends on a given limit.
After determining the allowable shift, create a 'mask'. This mask lets us grab the most significant bits from the second number. Think of the mask as a way to focus on the largest, most influential bits.
Use the mask to isolate the key bits from the second number. The more bits we can pull from the second number the better the OR result will be.
Shift the first number and OR it with the masked bits from the second number. This combines the two numbers to make the overall OR result as large as possible.
Return the final result. This represents the largest possible 'OR' value we can create by shifting and combining the two initial numbers.

Code Implementation

def maximum_or(number1, number2, shift_limit):
    # Determine how much we're allowed to shift number1
    allowable_shift = min(shift_limit, 32) 

    # Creates a mask to extract the significant bits from number2
    mask_for_significant_bits = (1 << allowable_shift) - 1

    # Applies the mask to isolate the key bits of number2
    significant_bits_from_number2 = number2 & mask_for_significant_bits

    # Shifts number1 to the left and combines it with the masked bits from number2
    shifted_number1 = number1 << allowable_shift
    final_result = shifted_number1 | significant_bits_from_number2

    return final_result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0 since no OR operation can be performed on an empty array.
k is 0 (no operations allowed)	Return the initial OR of the input array without any modifications.
Array contains only zero values.	The maximum OR value will always be 0 regardless of k, so return 0.
k is very large (larger than the array size * maximum bits needed to represent an element).	Consider each number multiplied by the largest possible power of 2 until k runs out or its representation reaches the upper bound of the datatype.
Integer overflow when multiplying a number by 2.	Use appropriate data types (e.g., long) to prevent integer overflow during multiplication.
Array contains very large numbers close to the maximum integer value.	Pay attention to how many times a number close to MAX_INT can be multiplied before overflow happens and adjust k accordingly.
All numbers are identical.	Multiply the first number nums[0] by 2 k times, then OR with all other nums[i] to obtain the maximum OR value.
k is large enough to potentially shift all the numbers such that the most significant bit of the resulting OR is set by the most significant bit of the largest number in the input array	The greedy approach should handle this automatically by focusing operations on the number contributing the most to the final OR result.

Empty input array (nums is null or has length 0)

How to Handle:

Return 0 since no OR operation can be performed on an empty array.

k is 0 (no operations allowed)

How to Handle:

Return the initial OR of the input array without any modifications.

Array contains only zero values.

How to Handle:

The maximum OR value will always be 0 regardless of k, so return 0.

k is very large (larger than the array size * maximum bits needed to represent an element).

How to Handle:

Consider each number multiplied by the largest possible power of 2 until k runs out or its representation reaches the upper bound of the datatype.

Integer overflow when multiplying a number by 2.

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during multiplication.

Array contains very large numbers close to the maximum integer value.

How to Handle:

Pay attention to how many times a number close to MAX_INT can be multiplied before overflow happens and adjust k accordingly.

All numbers are identical.

How to Handle:

Multiply the first number nums[0] by 2 k times, then OR with all other nums[i] to obtain the maximum OR value.

k is large enough to potentially shift all the numbers such that the most significant bit of the resulting OR is set by the most significant bit of the largest number in the input array

How to Handle:

The greedy approach should handle this automatically by focusing operations on the number contributing the most to the final OR result.