Shared Mask, Best Product

Medium

You are given non-negative integers first, second and bits. Choose a single mask x, 0 ≤ x < 2^bits, and XOR it into both numbers so that the product (first XOR x) · (second XOR x) is as large as possible. The result can be huge, so return it modulo 10⁹ + 7. Compare the options by their true product, not by the remainder.

Example 1

first=9, second=2, bits=3 → 84

With mask 3: 9 XOR 3 = 10 and 2 XOR 3 = 1, product 10. With mask 5: 9 XOR 5 = 12 and 2 XOR 5 = 7, product 84, which is the best.

Example 2

first=5, second=5, bits=0 → 25

With bits = 0 the only mask is 0, so the answer is 5 · 5 = 25.

Example 3

first=0, second=0, bits=2 → 9

Mask 3 turns both zeros into 3: 3 · 3 = 9.

Constraints

0 ≤ first, second < 2⁵⁰
0 ≤ bits ≤ 50

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Bit Manipulation Math

Similar problems

Division Without Dividing Medium Mirrored One-Bit Codes Medium Adding Without a Plus Medium Steps Down to One Medium Shared Pool Race to a Goal Medium

Input

first=9, second=2, bits=3

Expected

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