Jobs

Interviews

Discussions

Bitwise ORs of Subarrays

Medium

Amazon

4 views

Topics:

ArraysBit Manipulation

Given an integer array arr, return the number of distinct bitwise ORs of all the non-empty subarrays of arr.

The bitwise OR of a subarray is the bitwise OR of each integer in the subarray. The bitwise OR of a subarray of one integer is that integer.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: arr = [0]
Output: 1
Explanation: There is only one possible result: 0.

Example 2:

Input: arr = [1,1,2]
Output: 3
Explanation: The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

Example 3:

Input: arr = [1,2,4]
Output: 6
Explanation: The possible results are 1, 2, 3, 4, 6, and 7.

Constraints:

1 <= arr.length <= 5 * 10⁴
0 <= arr[i] <= 10⁹

Bitwise ORs of Subarrays

Medium

Amazon

4 views

Topics:

ArraysBit Manipulation

Given an integer array arr, return the number of distinct bitwise ORs of all the non-empty subarrays of arr.

The bitwise OR of a subarray is the bitwise OR of each integer in the subarray. The bitwise OR of a subarray of one integer is that integer.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: arr = [0]
Output: 1
Explanation: There is only one possible result: 0.

Example 2:

Input: arr = [1,1,2]
Output: 3
Explanation: The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

Example 3:

Input: arr = [1,2,4]
Output: 6
Explanation: The possible results are 1, 2, 3, 4, 6, and 7.

Constraints:

1 <= arr.length <= 5 * 10⁴
0 <= arr[i] <= 10⁹

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 size of the input array?
Can the input array contain negative numbers?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?
Should the output be the count of distinct bitwise OR values, or the set of distinct bitwise OR values themselves?
Is there a specific return value expected if the input array is empty or null?

Brute Force Solution

Approach

We need to find all the unique results you can get by combining numbers in different parts of a list using a special rule. The brute force approach is like trying every single possible part of the list and combining the numbers in it to see what results we get.

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

First, consider the result you get from just the first number in the list.
Then, consider the result from the first two numbers, then the first three, and so on, up to the entire list.
Next, start at the second number in the list and consider the result from just that number.
Then consider the result from the second and third numbers, the second, third, and fourth, and so on, up to the end of the list.
Keep repeating this process, each time starting one number later in the list, until you reach the last number alone.
Each time you combine the numbers in a part of the list, remember the result you get.
At the end, look at all the results you remembered, and remove any duplicates so you only have the unique results.

Code Implementation

def bitwise_ors_of_subarrays_brute_force(numbers):
    unique_results = set()

    # Iterate through each starting index of the subarray
    for start_index in range(len(numbers)): 
        current_bitwise_or = 0

        # Iterate through each ending index of the subarray, beginning at start_index
        for end_index in range(start_index, len(numbers)): 
            current_bitwise_or |= numbers[end_index]

            # Add the current bitwise OR to the set of unique results
            unique_results.add(current_bitwise_or)

    # Converting to list to return
    return list(unique_results)

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays of the input array of size n. The outer loop starts at each index i from 0 to n-1. The inner loop iterates from i to n-1, calculating the bitwise OR of the subarray starting at index i. Therefore, for each starting index i, the algorithm performs (n-i) operations. The total number of operations is approximately n + (n-1) + (n-2) + ... + 1, which is n*(n+1)/2. Simplifying this expression, the time complexity is O(n²).

Space Complexity

O(N) – The algorithm remembers all unique bitwise OR results encountered. In the worst-case scenario, where all subarrays produce unique bitwise OR results, the number of unique results could be proportional to the number of subarrays. The number of subarrays is roughly N*(N+1)/2, where N is the length of the input array. Thus, storing these unique results requires auxiliary space proportional to O(N^2). However, since a bitwise OR operation can only produce values between 0 and the maximum possible value representable within the bits of the integer which is constant, and the maximum possible unique value can only be N, the auxiliary space is O(N) since we use a set to store unique values. The set to store unique results dominates the space complexity.

Optimal Solution

Approach

The basic idea is that as you calculate the bitwise OR for growing sections, new bitwise OR values added by each number eventually stop introducing new values. We use this fact to avoid redundant calculations, focusing only on unique results from shorter sections to build longer ones efficiently.

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

Start by looking at each number in the collection individually. These are the starting bitwise OR values from sections of length one.
Now, go through the collection again, but this time, calculate the bitwise OR of sections of length two, then length three, and so on.
As you calculate these bitwise OR values, keep track of only the *unique* values you find. This is the key shortcut.
The reason this works is that, eventually, combining more numbers won't change the bitwise OR if the relevant bits are already 'on'.
By keeping track of only the unique bitwise OR values, you avoid recomputing the same results and greatly reduce the overall work.

Code Implementation

def bitwise_ors_of_subarrays(collection):
    unique_bitwise_or_values = set()
    current_bitwise_or_values = set()

    for number in collection:
        new_bitwise_or_values = set()

        # Starting point: each element itself.
        new_bitwise_or_values.add(number)
        unique_bitwise_or_values.add(number)

        # Calculate ORs with previous subarray ORs.
        for previous_bitwise_or in current_bitwise_or_values:
            new_bitwise_or = previous_bitwise_or | number
            new_bitwise_or_values.add(new_bitwise_or)
            unique_bitwise_or_values.add(new_bitwise_or)

        # Update the set of current OR values.
        current_bitwise_or_values = new_bitwise_or_values

    # Return all unique bitwise OR values.
    return list(unique_bitwise_or_values)

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n. For each element, it computes the bitwise OR with all subsequent subarrays starting from that element. The inner loop's length depends on the remaining size of the array, contributing to a nested loop structure. Therefore, in the worst case, the outer loop runs n times, and the inner loop runs up to n times, resulting in roughly n * n operations. The number of unique bitwise OR values stored also contributes to the space complexity, but does not affect the time complexity which remains dominated by the nested loop structure. Thus, the overall time complexity is O(n²).

Space Complexity

O(N) – The algorithm maintains a set of unique bitwise OR values encountered. In the worst-case scenario, where each subarray produces a different bitwise OR result, the set could potentially store up to N unique values in the first iteration, where N is the length of the input array. Subsequent iterations build upon this set, but the size is still bounded by the number of unique values which, at most, will be N. Therefore, the auxiliary space is proportional to N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input array	Return an empty set since there are no subarrays to process, avoiding null pointer exceptions and ensuring correct behavior.
Array with a single element	Return a set containing only that single element as the only possible subarray OR value.
Array with all elements equal to zero	The result should be a set containing only zero since the OR of any subarray will be zero.
Array with very large numbers (potential integer overflow)	Ensure the data type used to store the OR result (e.g., long) is large enough to accommodate the bitwise OR of the largest possible numbers to prevent overflow.
Array with all elements being the maximum integer value	The result will likely contain only the maximum integer value; handle memory efficiently since the intermediate set could grow large.
Array with repeating patterns that create identical ORs	Using a set to store the results ensures that we only store unique OR values, preventing duplicates from skewing the output and optimizing memory usage.
Very large array causing memory issues	Iterate through the array and compute ORs of subarrays, using a set to store distinct values; avoid storing all subarrays simultaneously to reduce memory footprint.
Negative numbers in the array (if applicable/allowed)	The bitwise OR operation will still function correctly with negative numbers, and the set will store their unique OR results assuming negative values are permissible in the prompt.

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 size of the input array?
Can the input array contain negative numbers?
Are duplicate numbers allowed in the input array, and if so, how should they be handled?
Should the output be the count of distinct bitwise OR values, or the set of distinct bitwise OR values themselves?
Is there a specific return value expected if the input array is empty or null?

Brute Force Solution

Approach

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

First, consider the result you get from just the first number in the list.
Then, consider the result from the first two numbers, then the first three, and so on, up to the entire list.
Next, start at the second number in the list and consider the result from just that number.
Then consider the result from the second and third numbers, the second, third, and fourth, and so on, up to the end of the list.
Keep repeating this process, each time starting one number later in the list, until you reach the last number alone.
Each time you combine the numbers in a part of the list, remember the result you get.
At the end, look at all the results you remembered, and remove any duplicates so you only have the unique results.

Code Implementation

def bitwise_ors_of_subarrays_brute_force(numbers):
    unique_results = set()

    # Iterate through each starting index of the subarray
    for start_index in range(len(numbers)): 
        current_bitwise_or = 0

        # Iterate through each ending index of the subarray, beginning at start_index
        for end_index in range(start_index, len(numbers)): 
            current_bitwise_or |= numbers[end_index]

            # Add the current bitwise OR to the set of unique results
            unique_results.add(current_bitwise_or)

    # Converting to list to return
    return list(unique_results)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by looking at each number in the collection individually. These are the starting bitwise OR values from sections of length one.
Now, go through the collection again, but this time, calculate the bitwise OR of sections of length two, then length three, and so on.
As you calculate these bitwise OR values, keep track of only the *unique* values you find. This is the key shortcut.
The reason this works is that, eventually, combining more numbers won't change the bitwise OR if the relevant bits are already 'on'.
By keeping track of only the unique bitwise OR values, you avoid recomputing the same results and greatly reduce the overall work.

Code Implementation

def bitwise_ors_of_subarrays(collection):
    unique_bitwise_or_values = set()
    current_bitwise_or_values = set()

    for number in collection:
        new_bitwise_or_values = set()

        # Starting point: each element itself.
        new_bitwise_or_values.add(number)
        unique_bitwise_or_values.add(number)

        # Calculate ORs with previous subarray ORs.
        for previous_bitwise_or in current_bitwise_or_values:
            new_bitwise_or = previous_bitwise_or | number
            new_bitwise_or_values.add(new_bitwise_or)
            unique_bitwise_or_values.add(new_bitwise_or)

        # Update the set of current OR values.
        current_bitwise_or_values = new_bitwise_or_values

    # Return all unique bitwise OR values.
    return list(unique_bitwise_or_values)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty set since there are no subarrays to process, avoiding null pointer exceptions and ensuring correct behavior.
Array with a single element	Return a set containing only that single element as the only possible subarray OR value.
Array with all elements equal to zero	The result should be a set containing only zero since the OR of any subarray will be zero.
Array with very large numbers (potential integer overflow)	Ensure the data type used to store the OR result (e.g., long) is large enough to accommodate the bitwise OR of the largest possible numbers to prevent overflow.
Array with all elements being the maximum integer value	The result will likely contain only the maximum integer value; handle memory efficiently since the intermediate set could grow large.
Array with repeating patterns that create identical ORs	Using a set to store the results ensures that we only store unique OR values, preventing duplicates from skewing the output and optimizing memory usage.
Very large array causing memory issues	Iterate through the array and compute ORs of subarrays, using a set to store distinct values; avoid storing all subarrays simultaneously to reduce memory footprint.
Negative numbers in the array (if applicable/allowed)	The bitwise OR operation will still function correctly with negative numbers, and the set will store their unique OR results assuming negative values are permissible in the prompt.