Clash-Free Flag Window

Medium

The array flags holds settings bitmasks: each positive number is a set of enabled flags. Call a contiguous stretch of the array *clash-free* if no two of its elements enable the same flag, that is, the bitwise AND of any two numbers at different positions in the stretch is 0. A stretch of one element is always clash-free. Return the length of the longest clash-free stretch.

Example 1

flags=[6, 1, 8, 16, 4, 2] → 5

The window [1, 8, 16, 4, 2] has no shared bits, length 5. The value 6 (bits 2 and 4) clashes with 4 and 2, so the whole array does not work.

Example 2

flags=[5, 7, 3] → 1

Every two neighbours share the bit 1, so only a single-element window works.

Constraints

1 ≤ len(flags) ≤ 10⁵
1 ≤ flags[i] < 2³¹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Sliding Window

Similar problems

Shortest Full-OR Stretch From Each Start Medium Short Window With a Big OR Medium Three-Lamp Switch Medium Light Every Lamp With a Window Hard XOR of a Close Pair Easy

Input

flags=[6, 1, 8, 16, 4, 2]

Expected

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