Skip to content

July 28, 2025 - Daily Drill

🎯 Daily Goals

  • Review Anki Deck
  • Lumosity training
  • Leetcode
  • Developing laplace
  • Langchain Learning

📝 What I learned:

898. Bitwise ORs of Subarrays

Thinking Process

It is easy to come up with a naive solution where we just check all subarrays and its bitwise or result and put them in a set. This would take O(n2) time. Since the input size is 5 * 10e4 this is not viable. Let's think incrementally. What if we know the solution of unique results of the previous arrays? With a new element coming in, we are only interested in the subarrays that ends with the new element. Denote the new element's index as k. To calculate the distinct bit wise ors of subarray ending in k, the best way is to keep track of the results of previous subarrays that ends in k - 1. Then we can just | with each of them and append k to it. This seems to be a linear time operation for each of the new element. However, if you take a closer look at the prompt you, would find that the arr[i] is bounded by [0, 10^9^] which has at most 32 bits. The bitwise ors we keep track of is incremental, thus we can have at most 32 elements in the frontier set.

Implementation

def bitwiseOperation(nums):
    frontier = set({0})
    result = set()
    for num in nums:
        frontier = {num | x for x in frontier} | {num}
        result |= frontier
    return len(result)

Complexity Analysis

Let the longest bit length of the element be m. And assume there is n elements in the array

  • Time Complexity: O(nlog(m))
  • Space Complexity: O(nm)

As we mentioned above, we would insert each element into set for n times. Each operation would take log(m) time. Thus O(nlog(m)) for time complexity. For space, assume for the worst case, each frontier set is different. The there would be n * m elements in stored in the result

🚀 Resources that Requires Further Study