Shifting Bits for Bigger Squares

Hard

You are given an array of positive integers values and an integer pick. As many times as you like, you may pick two different positions i and j and at the same moment replace values[i] with values[i] AND values[j] and values[j] with values[i] OR values[j] (bitwise AND and OR). When you are done, you choose pick elements of the array and add up their squares. Return the largest sum you can get, modulo 10⁹ + 7.

Example 1

values=[5, 5, 2], pick=2 → 74

Apply the operation to indices 1 and 2: 5 AND 2 = 0, 5 OR 2 = 7. The array becomes [5, 0, 7]; choose 7 and 5 for 49 + 25 = 74.

Example 2

values=[9, 6], pick=2 → 225

One operation gives [0, 15]. The squares add up to 0 + 225 = 225, more than the 81 + 36 = 117 you get without any operation.

Example 3

values=[3, 4, 1], pick=1 → 49

Constraints

1 ≤ pick ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Bit Manipulation Array Hash Table

Similar problems

Groups of Four at the Cinema Medium Narrowest Range Touching Every List Hard Triples With a Zero AND Hard Square-Sum Chains Hard Words That Fit Each Puzzle Hard

Input

values=[5, 5, 2], pick=2

Expected

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