AND Pieces With Cheap Tails

Hard

You are given an array of positive integers values of length n and an array targets of length m. Cut values into exactly m non-empty contiguous pieces (every element goes into exactly one piece and the order is kept) so that the bitwise AND of all elements in the j-th piece from the left equals targets[j]. The cost of a cut is the sum of the last elements of all pieces. Return the smallest possible cost, or -1 if no such cut exists.

Example 1

values=[6, 5, 12, 4, 7], targets=[4, 4] → 12

Two cuts work: [6, 5] | [12, 4, 7] (6 & 5 = 4, 12 & 4 & 7 = 4) and [6, 5, 12] | [4, 7] (6 & 5 & 12 = 4, 4 & 7 = 4). Their last elements add up to 5 + 7 = 12 and 12 + 7 = 19, so the answer is 12. Cutting as [6, 5, 12, 4] | [7] fails because the second piece has AND 7, not 4.

Example 2

values=[3, 3, 3], targets=[3] → 3

There is a single piece, the whole array; its AND is 3 and its last element is 3.

Example 3

values=[8, 1, 9], targets=[1, 9] → -1

The first piece needs AND 1, but 8 alone is 8 and 8 & 1 = 0, so no cut works and the answer is -1.

Constraints

1 ≤ n = len(values) ≤ 10⁴
1 ≤ m = len(targets) ≤ min(n, 10)
1 ≤ values[i] < 10⁵
0 ≤ targets[j] < 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Segment Tree Queue Array Binary Search Dynamic Programming

Similar problems

AND of a Stretch Near the Goal Hard Ferry Runs From the Depot Hard Two Equal Teams With Close Totals Hard Rising Chain With Small Steps Hard Steep Subsequence With the Largest Sum Hard

Input

values=[6, 5, 12, 4, 7], targets=[4, 4]

Expected

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