Skip to main content

Bitwise Subarray OR Threshold

medium
Bit ManipulationArrayBit Xor TrickTwo Pointer Partition
Asked atGoogleAmazonMeta

Problem Description

You are given an integer array `sequence` and an integer `floorVal`. Return the number of **contiguous subarrays** whose **bitwise OR** is greater than or equal to `floorVal`.

A subarray is a contiguous non-empty portion of the array.

**Example 1:**
```
Input: sequence = [3, 1, 5, 2], floorVal = 6
Output: 4
Explanation:
Subarrays and their OR values:
[3] → 3
[1] → 1
[5] → 5
[2] → 2
[3,1] → 3
[3,1,5] → 7 ✓
[3,1,5,2] → 7 ✓
[1,5] → 5
[1,5,2] → 7 ✓
[5,2] → 7 ✓
Four subarrays have OR ≥ 6.
```

**Example 2:**
```
Input: sequence = [8, 4, 2], floorVal = 8
Output: 4
Explanation:
[8] → 8 ✓, [8,4] → 12 ✓, [8,4,2] → 14 ✓, [4,2] → 6, [2] → 2, [4] → 4
Wait — [4,2]=6 no; [8,4,2]=14 ✓. Count = 4... let me recount:
[8]=8✓, [8,4]=12✓, [8,4,2]=14✓, [4]=4, [4,2]=6, [2]=2 → 3 subarrays ≥ 8.
Output: 3
```

**Example 2 (corrected):**
```
Input: sequence = [8, 4, 2], floorVal = 8
Output: 3
Explanation: [8]=8✓, [8,4]=12✓, [8,4,2]=14✓ are the qualifying subarrays.
```

Constraints

  • 1 <= sequence.length <= 1000
  • 1 <= sequence[i] <= 10^6
  • 1 <= floorVal <= 10^6

Follow-up

Can you solve the problem for all possible threshold values simultaneously in O(n log(max_val)) time by tracking the distinct OR values reachable from each left boundary?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.