We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Bitwise ORs of Subarrays

Number: 934

Difficulty: Medium

Paid? No

Companies: tcs

Problem Description

Given an integer array arr, return the number of distinct bitwise ORs of all the non-empty subarrays of arr. A subarray is a contiguous sequence of elements, and the bitwise OR of a subarray is the result of applying the OR operation to every element in that subarray.

Key Insights

  • Instead of evaluating every subarray explicitly, dynamic programming can be used to update the OR values for subarrays ending at each index.
  • When processing each element, all previous subarray OR results are combined (using bitwise OR) with the current element to capture the essence of extending subarrays.
  • A global set is maintained to collect all distinct OR results, avoiding duplicates.
  • The maximum number of distinct OR results from combining numbers is bounded by the number of bits, ensuring efficient processing.

Space and Time Complexity

Time Complexity: O(n * 32), which simplifies to O(n) due to the bounded number of bits. Space Complexity: O(n) in the worst-case for storing results in a set.

Solution

The algorithm maintains a temporary set, current_or_set, that contains all the distinct OR values ending at the current index. For each new element, it computes a new set by OR-ing the current element with each value in current_or_set and also adds the current element itself (representing subarrays that only include that element). This new set represents all distinct OR values for subarrays ending at the current element. These values are then added to a global set, distinct_results, to ensure all unique OR results are tracked throughout the array. The final answer is the size of distinct_results.

Code Solutions

def subarrayBitwiseORs(arr):
    # Set to store all distinct OR results.
    distinct_results = set()
    # Set to store OR results that end at the current element.
    current_or_set = set()
    
    for num in arr:
        # For the current element, start with the number itself.
        new_or_set = {num}
        # Extend previous subarrays by OR-ing with the current number.
        for previous in current_or_set:
            new_or_set.add(previous | num)
        # Update current_or_set for the next iteration.
        current_or_set = new_or_set
        # Add all new OR results to the global set.
        distinct_results.update(current_or_set)
    
    return len(distinct_results)

# Example test cases
print(subarrayBitwiseORs([0]))      # Expected output: 1
print(subarrayBitwiseORs([1,1,2]))    # Expected output: 3
print(subarrayBitwiseORs([1,2,4]))    # Expected output: 6
← Back to All Questions