2939. Maximum Xor Product
Description
Given three integers a
, b
, and n
, return the maximum value of (a XOR x) * (b XOR x)
where 0 <= x < 2n
.
Since the answer may be too large, return it modulo 109 + 7
.
Note that XOR
is the bitwise XOR operation.
Example 1:
Input: a = 12, b = 5, n = 4
Output: 98
Explanation: For x = 2, (a XOR x) = 14 and (b XOR x) = 7. Hence, (a XOR x) * (b XOR x) = 98.
It can be shown that 98 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.
Example 2:
Input: a = 6, b = 7 , n = 5 Output: 930 Explanation: For x = 25, (a XOR x) = 31 and (b XOR x) = 30. Hence, (a XOR x) * (b XOR x) = 930. It can be shown that 930 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.
Example 3:
Input: a = 1, b = 6, n = 3 Output: 12 Explanation: For x = 5, (a XOR x) = 4 and (b XOR x) = 3. Hence, (a XOR x) * (b XOR x) = 12. It can be shown that 12 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.
Constraints:
0 <= a, b < 250
0 <= n <= 50
Solutions
Solution 1: Greedy + Bitwise Operation
According to the problem description, we can assign a number to the $[0..n)$ bits of $a$ and $b$ in binary at the same time, so that the product of $a$ and $b$ is maximized.
Therefore, we first extract the parts of $a$ and $b$ that are higher than the $n$ bits, denoted as $ax$ and $bx$.
Next, we consider each bit in $[0..n)$ from high to low. We denote the current bits of $a$ and $b$ as $x$ and $y$.
If $x = y$, then we can set the current bit of $ax$ and $bx$ to $1$ at the same time. Therefore, we update $ax = ax \mid 1 << i$ and $bx = bx \mid 1 << i$. Otherwise, if $ax < bx$, to maximize the final product, we should set the current bit of $ax$ to $1$. Otherwise, we can set the current bit of $bx$ to $1$.
Finally, we return $ax \times bx \bmod (10^9 + 7)$ as the answer.
The time complexity is $O(n)$, where $n$ is the integer given in the problem. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|