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 < 2500 <= 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
| class Solution:
def maximumXorProduct(self, a: int, b: int, n: int) -> int:
mod = 10**9 + 7
ax, bx = (a >> n) << n, (b >> n) << n
for i in range(n - 1, -1, -1):
x = a >> i & 1
y = b >> i & 1
if x == y:
ax |= 1 << i
bx |= 1 << i
elif ax > bx:
bx |= 1 << i
else:
ax |= 1 << i
return ax * bx % mod
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int maximumXorProduct(long a, long b, int n) {
final int mod = (int) 1e9 + 7;
long ax = (a >> n) << n;
long bx = (b >> n) << n;
for (int i = n - 1; i >= 0; --i) {
long x = a >> i & 1;
long y = b >> i & 1;
if (x == y) {
ax |= 1L << i;
bx |= 1L << i;
} else if (ax < bx) {
ax |= 1L << i;
} else {
bx |= 1L << i;
}
}
ax %= mod;
bx %= mod;
return (int) (ax * bx % mod);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int maximumXorProduct(long long a, long long b, int n) {
const int mod = 1e9 + 7;
long long ax = (a >> n) << n, bx = (b >> n) << n;
for (int i = n - 1; ~i; --i) {
int x = a >> i & 1, y = b >> i & 1;
if (x == y) {
ax |= 1LL << i;
bx |= 1LL << i;
} else if (ax < bx) {
ax |= 1LL << i;
} else {
bx |= 1LL << i;
}
}
ax %= mod;
bx %= mod;
return ax * bx % mod;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func maximumXorProduct(a int64, b int64, n int) int {
const mod int64 = 1e9 + 7
ax := (a >> n) << n
bx := (b >> n) << n
for i := n - 1; i >= 0; i-- {
x, y := (a>>i)&1, (b>>i)&1
if x == y {
ax |= 1 << i
bx |= 1 << i
} else if ax < bx {
ax |= 1 << i
} else {
bx |= 1 << i
}
}
ax %= mod
bx %= mod
return int(ax * bx % mod)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| function maximumXorProduct(a: number, b: number, n: number): number {
const mod = BigInt(1e9 + 7);
let ax = (BigInt(a) >> BigInt(n)) << BigInt(n);
let bx = (BigInt(b) >> BigInt(n)) << BigInt(n);
for (let i = BigInt(n - 1); ~i; --i) {
const x = (BigInt(a) >> i) & 1n;
const y = (BigInt(b) >> i) & 1n;
if (x === y) {
ax |= 1n << i;
bx |= 1n << i;
} else if (ax < bx) {
ax |= 1n << i;
} else {
bx |= 1n << i;
}
}
ax %= mod;
bx %= mod;
return Number((ax * bx) % mod);
}
|
