Ctrl K

Distinct Window ORs

Medium
You are given an array values of non-negative integers. For every non-empty window of consecutive elements, take the bitwise OR (|) of all its elements. The OR of a one-element window is that element itself. How many distinct values come out? Return their count.
Example 1
values=[4, 1, 4] → 3

The windows give 4, 1, 4, 4 | 1 = 5, 1 | 4 = 5 and 4 | 1 | 4 = 5. There are three distinct values: 1, 4, 5.

Example 2
values=[3, 3, 3] → 1

Every window gives 3.

Example 3
values=[1, 2, 4, 8] → 10

All 10 windows give different values: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15.

Constraints
  • 1 ≤ len(values) ≤ 5 · 10⁴
  • 0 ≤ values[i] ≤ 10⁹
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsSquare Frame From Sticks MediumSeating by Divisibility MediumCheapest Basket with Bundles MediumGroups With Equal Sums MediumLeast Total Walk to Scooters Medium
loading Python…
Input
values=[4, 1, 4]
Expected
3

Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.