Stretches With an Exact AND

Hard

You get an array of non-negative integers values and a number goal. A stretch is a non-empty run of consecutive elements of the array. Return the number of stretches whose bitwise AND over all elements is exactly goal. Stretches with the same values but at different positions count separately.

Example 1

values=[7, 6, 14, 6], goal=6 → 8

The AND is 6 for [6], [6], [7, 6], [6, 14], [14, 6], [6, 14, 6], [7, 6, 14] and [7, 6, 14, 6]: 8 stretches.

Example 2

values=[3, 5, 3], goal=1 → 3

3 AND 5 = 1, so [3, 5], [5, 3] and [3, 5, 3] work; the single elements are 3 or 5.

Example 3

values=[4, 8], goal=2 → 0

Constraints

1 ≤ len(values) ≤ 10⁵
0 ≤ values[i], goal ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Segment Tree Array Binary Search

Similar problems

AND of a Stretch Near the Goal Hard AND Pieces With Cheap Tails Hard Window OR Closest to a Target Hard Smaller Values to the Right Hard Window Sums Within a Band Hard

Input

values=[7, 6, 14, 6], goal=6

Expected

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