898. Bitwise ORs of Subarrays

Array Math Dynamic Programming Bit Manipulation

Time: O(n log max)

Space: O(n log max)

Intuition

Maintain set of all OR values of subarrays ending at current position. Size bounded by 32 (bits can only be set, not cleared). Union all sets for answer.

Algorithm

1cur = empty set.
2For each A[i]: new_cur = {x|A[i] for x in cur} union {A[i]}.
3Add new_cur elements to result set.
4Return result set size.

Common Pitfalls

•Set size is O(32) per position since ORs are monotonically non-decreasing.

898.cs

// Approach: Maintain a rolling set of OR values of all subarrays ending at the current index; add all values to the global distinct set.
// Time: O(n log max) Space: O(n log max)

using System.Collections.Generic;

public class Solution
{
    public int SubarrayBitwiseORs(int[] arr)
    {
        HashSet<int> result = new HashSet<int>();
        HashSet<int> current = new HashSet<int>();
        
        foreach (int num in arr)
        {
            HashSet<int> next = new HashSet<int>();
            next.Add(num);
            
            foreach (int val in current)
            {
                next.Add(val | num);
            }
            
            current = next;
            
            foreach (int val in current)
            {
                result.Add(val);
            }
        }
        
        return result.Count;
    }
}

Was this solution helpful?