AND of a Stretch Near the Goal

Hard

You are given an array of positive integers values and an integer goal. For any contiguous non-empty stretch of the array you can compute the bitwise AND (&) of all its elements. Return the smallest possible value of |AND(stretch) - goal| over all stretches. There are O(n²) stretches, but for a fixed right end only a few distinct AND values appear: think about why.

Example 1

values=[12, 10, 6, 7], goal=5 → 1

The stretches give 12, 10, 6, 7, 12 & 10 = 8, 10 & 6 = 2, 6 & 7 = 6, plus 0 and 2 for the longer ones. The closest to 5 is 6, a difference of 1.

Example 2

values=[9, 9, 9], goal=20 → 11

Every stretch gives 9, a difference of 11.

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁶
0 ≤ 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 Pieces With Cheap Tails Hard Window OR Closest to a Target Hard Stretches With an Exact AND Hard Smaller Values to the Right Hard Window Sums Within a Band Hard

Input

values=[12, 10, 6, 7], goal=5

Expected

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