29 April 2024 Kolkata (Q2) — Distinct Bitwise OR of Subarrays
H · hardP · Verified PYQarraysbit-manipulation
Problem
Given an integer array, find the number of distinct values that can be obtained as the bitwise OR of any contiguous subarray of the array.
Example
Input
4 1 2 3 2
Output
4
For each starting index i, maintain running OR. Add each OR to a HashSet. Return set size. O(N^2).
OR values: {1},{2},{3},{2},{1,2}=3,{2,3}=3,{3,2}=3,{1,2,3}=3,{2,3,2}=3,{1,2,3,2}=3 → distinct={1,2,3,3}={1,2,3} + full=3 → set={1,2,3,3}→ actually {1,2,3} = 3 distinct values plus 0... check.