Skip to main content
Talentd

Maximum Xor Product - Solution & Explanation

MediumMathGreedyBit Manipulation19 min readAsked at: Atlassian, Google, Rippling +1
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given integers a, b, and n. Choose a number x such that 0 ≤ x < 2^n and maximize the product (a XOR x) * (b XOR x). Only the lowest n bits of x can change the result, so the task reduces to carefully choosing which of those bits to flip.

Approach 1: Brute Force Enumeration (O(2^n) time, O(1) space)

Try every possible value of x from 0 to 2^n - 1. For each candidate, compute a ^ x and b ^ x, multiply them, and track the maximum product. This approach directly follows the problem definition and uses basic bit manipulation operations. The downside is exponential growth: if n is large, iterating over all 2^n possibilities becomes infeasible. It works only when n is very small or when building intuition during early experimentation.

Approach 2: Optimized Binary Greedy Construction (O(n) time, O(1) space)

The product (a ^ x) * (b ^ x) is maximized when the two resulting numbers are both large and as balanced as possible. Instead of testing every x, build the result bit by bit from the most significant of the n adjustable bits down to the least significant. This uses a greedy strategy based on how XOR affects each bit.

For each bit position i in the range [0, n-1], inspect the corresponding bits in a and b. If the bits are equal, setting the bit in x to flip both values to 1 increases both numbers simultaneously, which improves the product. If the bits differ, only one of the two results can gain a 1. In that case, assign the bit so the smaller current value receives the 1. This greedy balancing step keeps the two numbers closer together, which maximizes their multiplication result. The technique combines ideas from greedy algorithms and math properties of products.

Bits above position n-1 remain unchanged because x cannot affect them. As you iterate through the controllable bits, update the partially constructed values of a ^ x and b ^ x. The final numbers yield the maximum product without exploring the full search space.

Recommended for interviews: Interviewers expect the greedy bit manipulation approach. The brute force method demonstrates understanding of XOR behavior, but the optimized approach shows you recognize that maximizing a product favors large, balanced operands and that bit decisions can be made independently from most significant to least significant.

Approach 1: Brute Force Approach

The brute force approach involves iterating through all values of x from 0 to 2n - 1. For each x, compute (a XOR x) * (b XOR x) and keep track of the maximum value encountered. This approach is straightforward but not efficient for large values of n due to the exponential number of calculations involved.

This C program uses a simple for loop to iterate over all possible values of x from 0 to 2n-1. For each x, it computes the XOR product and checks if it's the maximum encountered so far. The result is obtained modulo 109 + 7.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2n), Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Optimized Binary Manipulation Approach

To optimize, note that the highest bits have the greatest impact on the result. We can iterate only once, while considering the impact of x near (1 << n) - 1 or by choosing x that maximizes the resulting bits in XOR operations, effectively reducing unnecessary iterations.

This C code attempts to further optimize the solution by focusing on values of x derived from setting and unsetting specific bits. This method particularly focuses on dominating bit manipulations pausing only on those with the highest potential XOR.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(1)

Try this approach in the editor →

Approach 3: 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(2n), Space Complexity: O(1)

Optimized Binary Manipulation Approach

Time Complexity: O(n), Space Complexity: O(1)

Greedy + Bitwise Operation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(2^n)O(1)Useful for very small n or verifying correctness during testing
Greedy Bit ManipulationO(n)O(1)Optimal solution for large n; builds the best result bit by bit

Video Solution

Maximum Xor Product | Super Detailed | Leetcode Weekly Contest 372 | Leetcode-2939 • codestorywithMIK • 11,953 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Maximum Xor Product easy or hard?
Maximum Xor Product is typically rated Medium difficulty. The brute force idea is straightforward, but recognizing that the optimal solution can be built greedily using bit manipulation requires deeper insight into XOR behavior and how products are maximized.
How to solve Maximum Xor Product in O(n)?
Iterate through the n controllable bits from most significant to least significant. Examine the corresponding bits in a and b and decide whether to flip them using x. If the bits are equal, flip them so both become 1. If they differ, assign the bit so the smaller current value receives the 1. This greedy balancing maximizes the final product.
What is the best approach for Maximum Xor Product?
The best approach uses greedy bit manipulation. Instead of testing every possible x, construct the result bit by bit from the most significant adjustable bit. When the bits of a and b are equal, flip them to produce 1s in both numbers. When they differ, assign the bit so the smaller value gains the 1, keeping the product maximized. This runs in O(n) time and O(1) space.
What data structure is used in Maximum Xor Product?
No complex data structure is required. The solution relies on bitwise operations such as shifts, XOR, and bit masking. The main idea is analyzing individual bits and greedily constructing the optimal result.
What is the time complexity of Maximum Xor Product?
The optimal greedy solution runs in O(n) time where n is the number of bits you are allowed to modify. Each bit from 0 to n-1 is processed once. The space complexity is O(1) because only a few integer variables are maintained during the computation.
Maximum Xor Product Python or Java solution approach?
Both Python and Java implementations follow the same logic: iterate over the n bits, inspect bits from a and b, and greedily decide whether the bit in x should flip them. Maintain the running values of a XOR x and b XOR x while processing bits. The algorithm remains O(n) time and O(1) space regardless of language.
Is Maximum Xor Product asked at Google, Amazon, or Meta?
Bit manipulation and greedy optimization problems like Maximum Xor Product frequently appear in interviews at companies such as Google, Amazon, and Meta. The problem tests understanding of XOR behavior, bitwise construction, and reasoning about how to maximize a mathematical expression efficiently.

Ready to solve this problem?

Practice Maximum Xor Product with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum XOR After Operations