2939. Maximum Xor Product
Problem Description
Given three integers a
, b
, and n
, the task is to find the maximum value of (a XOR x) * (b XOR x)
where x
can be any integer from 0
to 2^n - 1
(both inclusive). Here, XOR
refers to the bitwise exclusive OR operation. To ensure the return value is within a manageable size, we are asked to return the result after taking the modulo of 10^9 + 7
.
We know that the XOR operation can flip bits in the binary representation of a number, depending on the bits of another number it is being XORed with. The catch here is to intelligently select the value of x
that, when XORed with a
and b
, results in the maximum possible product (a XOR x) * (b XOR x)
.
Intuition
The solution follows a greedy approach combined with bitwise operations. The intuition behind the solution lies in understanding how the XOR operation affects the bits of the operands and consequently, the product of the two results. The XOR operation with 1
flips a bit, while XOR with 0
leaves it unchanged. The goal is to carefully set each bit of x
to either 0
or 1
in such a way that the resulting product is maximized.
The process starts with ensuring that the most significant bits (those beyond n
) of a
and b
are preserved as they will always contribute to the larger value in the product when XORed with 0
. These parts are denoted as ax
and bx
respectively.
Then, for each bit from the most significant bit n-1
to the least significant bit 0
, we decide whether to set the corresponding bit in ax
and bx
to 1
. If the current bits of a
and b
are equal, setting the bit to 1
in both ax
and bx
does not change their product, but as these bits are less significant than the preserved parts, it is optimal to set them to 1
.
However, when the bits of a
and b
are different, we have a decision to make. To increase the product, we want to flip the bit of the smaller operand among ax
and bx
. This way, we are increasing the smaller number without decreasing the other, thus maximizing the product.
By iterating from the most significant bit to the least significant bit in this manner and updating ax
and bx
accordingly, we ensure that we arrive at the highest possible product. Once we have determined the optimal ax
and bx
, the final result is their product, modulo 10^9 + 7
.
Solution Approach
The solution approach makes clever use of bitwise operations to arrive at the maximum product. Here's how the algorithm proceeds:
-
The first step is to preserve the bits of
a
andb
that are above then-th
bit since those are not affected by XOR with anyx
in the given range0
to2^n - 1
.- This is done by right-shifting
a
andb
byn
and then left-shifting back byn
. The result is stored in two new variablesax
andbx
. This effectively zeroes out the bits in positions0
ton-1
since right-shifting followed by left-shifting with the same number of bits fills the vacated bits with zeroes.
- This is done by right-shifting
-
The core of the algorithm then iterates over each bit position from
n-1
down to0
:- For each bit position
i
, we extract the bit value ofa
andb
at positioni
using the bitwise AND operation with1 << i
. - Next, we determine if the current bits of
a
andb
, letās call themx
andy
, are the same or not. If they are the same, then regardless of what valuex
takes for bit positioni
, the product will be maximized if the bit positioni
is set to1
for bothax
andbx
.
- For each bit position
-
However, if
x
andy
are not equal, we compare the values ofax
andbx
. We only want to flip the bit of the smaller value between the two:- If
ax
is greater thanbx
, then we increasebx
by setting itsi-th
bit to ensurebx
is increased. - Conversely, if
bx
is greater or equal toax
, then we increaseax
by setting itsi-th
bit. - This operation intends to make
bx
andax
more equal in value, as the maximum product of two numbers happens when they are closest to each other in value.
- If
-
After determining the optimal
ax
andbx
, we calculate the product and take the modulo with10^9 + 7
to get the final result:ax * bx % mod
Each of these steps complies with the greedy paradigm of algorithm design, as we are making the locally optimal choice of setting bit i
in hope of finding the global maximum product. By considering bit positions in a descending order, we prioritize the influence of higher-order bits on the product, which is key since they contribute significantly more to the value than lower-order bits.
In terms of data structures, no additional structures are necessary; the solution uses basic integer variables to store the modified versions of a
and b
, as well as to handle intermediate values as we iterate over the bits.
By breaking down the bitwise operations and decision-making process, we can see exactly how the algorithm maximizes the final product and ensure that it conforms to the constraints and requirements described in the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Assume we are given a = 22
, b = 27
, and n = 5
. The binary representations of a
and b
within 5 bits are 10110
for a
and 11011
for b
. We aim to find an x
such that (a XOR x) * (b XOR x)
is maximized, where x
ranges from 0
to 2^5 - 1
, i.e., 0
to 31
.
Step 1: Since n
equals 5
, we do not need to alter a
and b
for this particular example because any x
within the range will not affect bits beyond the 5th bit.
Step 2: We start iterating from the 4th bit (most significant bit) to the 0th bit (least significant bit):
For the 4th bit (2^4
or 16
place):
a
at 4th bit is1
,b
at 4th bit is1
. Both are the same. We choosex
to have0
at this bit to keep the bits intact and maintain the high value.
For the 3rd bit (2^3
or 8
place):
a
at 3rd bit is0
,b
at 3rd bit is1
. They differ. We want to flip the bit for the smaller operand of the two (for our purposes, since their bits beyondn
are zero,ax
andbx
correspond toa
andb
). Sox
will have1
at this bit to flipa
's 3rd bit and make it larger.
For the 2nd bit (2^2
or 4
place):
- Both
a
andb
have1
at this bit. No changes needed; we choosex
to have0
at this bit.
For the 1st bit (2^1
or 2
place):
a
at 1st bit is1
,b
at 1st bit is0
. They are different again, andb
is smaller at the 1st bit. We choosex
to have1
at this bit to flipb
's 1st bit.
For the 0th bit (2^0
or 1
place):
a
at 0th bit is0
,b
at 0th bit is1
. We flipa
's 0th bit by choosingx
to have1
at this bit.
Based on the decisions above, for each bit, x
will be 01111
in binary or 15
in decimal.
Step 3: Now we compute (a XOR x) * (b XOR x)
:
(a XOR x)
in binary:10110 XOR 01111
equals11001
(decimal25
)(b XOR x)
in binary:11011 XOR 01111
equals10100
(decimal20
)
Step 4: The product is 25 * 20 = 500
. The modulo operation is not needed in this specific case because the product is already less than 10^9 + 7
.
Thus, the maximum value for (a XOR x) * (b XOR x)
is 500
for x = 15
.
This example demonstrates the step-by-step process described in the solution approach by carefully constructing the optimal value of x
using bitwise operations to maximize the product.
Solution Implementation
1class Solution:
2 def maximum_xor_product(self, num1: int, num2: int, num_bits: int) -> int:
3 # Define the modulus for taking the result % mod
4 MODULUS = 10**9 + 7
5
6 # Initialize variables to store the maximum XOR values based on the most significant bits
7 xor_num1, xor_num2 = (num1 >> num_bits) << num_bits, (num2 >> num_bits) << num_bits
8
9 # Iterate over each bit, from most significant bit to least significant bit
10 for i in range(num_bits - 1, -1, -1):
11 # Extract the current bit of num1 and num2
12 bit_num1 = (num1 >> i) & 1
13 bit_num2 = (num2 >> i) & 1
14
15 # If the current bits are equal, set the current bit in both xor_num1 and xor_num2
16 if bit_num1 == bit_num2:
17 xor_num1 |= 1 << i
18 xor_num2 |= 1 << i
19 # If xor_num1 is greater, set the current bit in xor_num2
20 elif xor_num1 > xor_num2:
21 xor_num2 |= 1 << i
22 # Otherwise, set the current bit in xor_num1
23 else:
24 xor_num1 |= 1 << i
25
26 # Return the product of xor_num1 and xor_num2 modulo MODULUS
27 return (xor_num1 * xor_num2) % MODULUS
28
1class Solution {
2 public int maximumXorProduct(long num1, long num2, int bits) {
3 final int MODULUS = (int) 1e9 + 7; // The modulus value for the result
4
5 // These two variables represent num1 and num2 with the last 'bits' bits set to 0
6 long adjustedNum1 = (num1 >> bits) << bits;
7 long adjustedNum2 = (num2 >> bits) << bits;
8
9 // Iterate over each bit from 'bits-1' down to 0
10 for (int i = bits - 1; i >= 0; --i) {
11 long bitNum1 = (num1 >> i) & 1; // Get the ith bit of num1
12 long bitNum2 = (num2 >> i) & 1; // Get the ith bit of num2
13
14 // If ith bits of num1 and num2 are equal, set ith bits of adjustedNum1 and adjustedNum2 to 1
15 if (bitNum1 == bitNum2) {
16 adjustedNum1 |= 1L << i;
17 adjustedNum2 |= 1L << i;
18 }
19 // Otherwise, if adjustedNum1 is less than adjustedNum2, set ith bit of adjustedNum1 to 1
20 else if (adjustedNum1 < adjustedNum2) {
21 adjustedNum1 |= 1L << i;
22 }
23 // Otherwise, set ith bit of adjustedNum2 to 1
24 else {
25 adjustedNum2 |= 1L << i;
26 }
27 }
28
29 // Apply modulus operation to both adjusted numbers to ensure the product is within the range
30 adjustedNum1 %= MODULUS;
31 adjustedNum2 %= MODULUS;
32
33 // Calculate the product of adjustedNum1 and adjustedNum2, apply modulus operation, and cast to integer
34 return (int) (adjustedNum1 * adjustedNum2 % MODULUS);
35 }
36}
37
1class Solution {
2public:
3 int maximumXorProduct(long long numA, long long numB, int n) {
4 const int MOD = 1e9 + 7; // Define the modulo constant for the result
5
6 // Initialize `aXor` and `bXor` by preserving the higher bits up to `n` and setting lower bits to 0
7 long long aXor = (numA >> n) << n;
8 long long bXor = (numB >> n) << n;
9
10 // Iterate bit positions from n-1 down to 0
11 for (int bitPos = n - 1; bitPos >= 0; --bitPos) {
12 // Extract the bit at `bitPos` for both `numA` and `numB`
13 int bitA = (numA >> bitPos) & 1;
14 int bitB = (numB >> bitPos) & 1;
15
16 // If the bits are the same, set the bit at `bitPos` in both `aXor` and `bXor`
17 if (bitA == bitB) {
18 aXor |= 1LL << bitPos;
19 bXor |= 1LL << bitPos;
20 } else if (aXor < bXor) {
21 // If `aXor` is less than `bXor`, set the bit in `aXor`
22 aXor |= 1LL << bitPos;
23 } else {
24 // Otherwise, set the bit in `bXor`
25 bXor |= 1LL << bitPos;
26 }
27 }
28
29 // Apply the modulo operation to both `aXor` and `bXor`
30 aXor %= MOD;
31 bXor %= MOD;
32
33 // Return the product of `aXor` and `bXor` under modulo
34 return (aXor * bXor) % MOD;
35 }
36};
37
1function maximumXorProduct(a: number, b: number, n: number): number {
2 // Define the modulus for the final result to avoid large numbers
3 const MOD = BigInt(1e9 + 7);
4
5 // Initialize ax and bx to only include the bits from a and b above the nth bit
6 // This effectively zeroes out the last n bits
7 let ax = (BigInt(a) >> BigInt(n)) << BigInt(n);
8 let bx = (BigInt(b) >> BigInt(n)) << BigInt(n);
9
10 // Loop over each bit from n-1 down to 0
11 for (let i = BigInt(n - 1); i >= 0; --i) {
12 // Extract the ith bit from both a and b
13 const aBit = (BigInt(a) >> i) & 1n;
14 const bBit = (BigInt(b) >> i) & 1n;
15
16 // If the bits are equal, set the ith bit of both ax and bx
17 if (aBit === bBit) {
18 ax |= 1n << i;
19 bx |= 1n << i;
20 }
21 // If ax is currently less than bx, set the ith bit of ax
22 else if (ax < bx) {
23 ax |= 1n << i;
24 }
25 // Otherwise, set the ith bit of bx
26 else {
27 bx |= 1n << i;
28 }
29 }
30
31 // Reduce ax and bx by the modulus to handle overflow
32 ax %= MOD;
33 bx %= MOD;
34
35 // Calculate the product of ax and bx, reduce it by the modulus,
36 // and return the number representation of the result
37 return Number((ax * bx) % MOD);
38}
39
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n)
. Here, n
refers to the value given as an argument to the function, not the size of any input array or list, as might typically be the case in algorithmic problems. The code iterates from n - 1
down to 0 via the for loop, resulting in exactly n
iterations, hence the time complexity is linear with respect to n
.
Space Complexity
The space complexity of the code is O(1)
. This analysis is straightforward as the function operates in constant space, using a fixed number of integer variables (mod
, ax
, bx
, i
, x
, y
) regardless of the value of n
or the size of the input numbers a
and b
. There are no data structures used that grow with the size of the input, which confirms that the space requirements remain constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!