Merge Neighbors for a Small OR

Hard

You are given an array of non-negative integers values and an integer merges. In one operation you take two **adjacent** elements and replace them with a single element equal to their bitwise AND (&), so the array gets one element shorter. Using at most merges operations, make the bitwise OR of all remaining elements as small as possible. Return that value.

Example 1

values=[12, 10, 3, 1], merges=2 → 1

Merge the first three numbers: 12 AND 10 = 8, then 8 AND 3 = 0. That leaves [0, 1] with an OR of 1. Zero is out of reach: whichever piece holds the final 1 would have to swallow 3, 10 and 12 too, which takes 3 merges.

Example 2

values=[7, 7, 7], merges=2 → 7

The AND of equal numbers changes nothing, so the answer is 7 whatever we merge.

Example 3

values=[5, 2, 6, 1], merges=1 → 7

Constraints

1 ≤ len(values) ≤ 10⁵
0 ≤ values[i] < 2³⁰
0 ≤ merges < len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Bit Manipulation Array

Similar problems

Break Coins for an Exact Payment Hard Shifting Bits for Bigger Squares Hard Edge Toggles on a Tree Hard Best Binary Rows After Flips Medium Groups of Four at the Cinema Medium

Input

values=[12, 10, 3, 1], merges=2

Expected

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