Two Halves: OR, Then XOR

Hard

You are given an array values and a number half. Choose exactly 2 · half elements, keeping their original order. The first half chosen elements form the left half, the remaining half form the right half. The worth of a choice is (OR of the left half) XOR (OR of the right half), where OR and XOR are bitwise. Return the greatest possible worth.

Example 1

values=[3, 5, 6], half=1 → 6

Pick 3 and 5: 3 XOR 5 = 6. The pairs (3, 6) and (5, 6) give 5 and 3.

Example 2

values=[1, 2, 4, 8, 3], half=2 → 15

Pick 1, 2, 4, 8: (1 OR 2) XOR (4 OR 8) = 3 XOR 12 = 15.

Constraints

2 ≤ len(values) ≤ 400
1 ≤ values[i] < 2⁷
1 ≤ half ≤ len(values) / 2

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Dynamic Programming

Similar problems

Settle Up in the Fewest Transfers Hard Two Groups With the Same Average Hard Assembling Fragments Hard Square-Sum Chains Hard Smallest Team With Every Skill Hard

Input

values=[3, 5, 6], half=1

Expected

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