Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximum Xor Product solution and explanation

MediumBit ManipulationGreedyMath7 min read30.3% acceptanceUpdated 9 Apr 2026
Asked atSquarepoint CapitalRipplingAtlassianGoogle
Practise Maximum Xor Product
58:42
Maximum Xor Product | Super Detailed | Leetcode Weekly Contest 372 | Leetcode-2939codestorywithMIK · 58:42 · 11K viewsWatch on YouTube
6 more videos on this problem
  1. Maximum Xor Product | Super Detailed | Leetcode Weekly Contest 372 | Leetcode-2939codestorywithMIK · 58:42 · 11K views
  2. 2939. Maximum Xor Product | Weekly Leetcode 372codingMohan · 18:37 · 2K views
  3. 2939. Maximum Xor ProductAyush Rao · 9:35 · 2K views
  4. 2939. Maximum XOR Product | Leetcode Contest 372 | Intuition, Approach and Code | Optimal Solution🔥CodeVichar · 15:45 · 660 views
  5. 2939. Maximum Xor Product || Leetcode Weekly Contest 372Ashish Kumar · 26:06 · 350 views
  6. Maximum Xor Product - LeetCode 2939 - PythonAlpha-Code · 23:51 · 135 views
  7. Maximum Xor Product - LeetCode 2939 | Best Intuition + Easy Approach #leetcodesolution #leetcodeCodehurdle · 14:38 · 128 views

The problem

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.

def max_xor_product(a, b, n):
    MOD = 1000000007
    max_product = 0
    for x in range(1 << n):
        xor_a = a ^ x
        xor_b = b ^ x
        prod = (xor_a * xor_b) % MOD
        max_product = max(max_product, prod)
    return max_product

# Example Usage
print(max_xor_product(12, 5, 4))
public class MaxXorProduct {
    private static final int MOD = 1000000007;
    
    public static long maxXorProduct(int a, int b, int n) {
        long maxProduct = 0;
        for (int x = 0; x < (1 << n); x++) {
            long xorA = a ^ x;
            long xorB = b ^ x;
            long prod = (xorA * xorB) % MOD;
            maxProduct = Math.max(maxProduct, prod);
        }
        return maxProduct;
    }
    
    public static void main(String[] args) {
        int a = 12, b = 5, n = 4;
        System.out.println(maxXorProduct(a, b, n));
    }
}
#include <iostream>
#define MOD 1000000007

using namespace std;

long long maxXorProduct(int a, int b, int n) {
    long long maxProduct = 0;
    for (int x = 0; x < (1 << n); x++) {
        long long xorA = a ^ x;
        long long xorB = b ^ x;
        long long prod = (xorA * xorB) % MOD;
        maxProduct = max(maxProduct, prod);
    }
    return maxProduct;
}

int main() {
    int a = 12, b = 5, n = 4;
    cout << maxXorProduct(a, b, n) << endl;
    return 0;
}
function maxXorProduct(a, b, n) {
    const MOD = 1000000007;
    let maxProduct = 0;
    for (let x = 0; x < (1 << n); x++) {
        let xorA = a ^ x;
        let xorB = b ^ x;
        let prod = (xorA * xorB) % MOD;
        maxProduct = Math.max(maxProduct, prod);
    }
    return maxProduct;
}

console.log(maxXorProduct(12, 5, 4));
#include <stdio.h>
#define MOD 1000000007

long long maxXorProduct(int a, int b, int n) {
    long long maxProduct = 0;
    for (int x = 0; x < (1 << n); x++) {
        long long xorA = a ^ x;
        long long xorB = b ^ x;
        long long prod = (xorA * xorB) % MOD;
        if (prod > maxProduct) {
            maxProduct = prod;
        }
    }
    return maxProduct;
}

int main() {
    int a = 12, b = 5, n = 4;
    printf("%lld\n", maxXorProduct(a, b, n));
    return 0;
}
using System;

public class MaxXorProduct {
    private const int MOD = 1000000007;

    public static long MaxXorProduct(int a, int b, int n) {
        long maxProduct = 0;
        for (int x = 0; x < (1 << n); x++) {
            long xorA = a ^ x;
            long xorB = b ^ x;
            long prod = (xorA * xorB) % MOD;
            if (prod > maxProduct) maxProduct = prod;
        }
        return maxProduct;
    }

    public static void Main() {
        int a = 12, b = 5, n = 4;
        Console.WriteLine(MaxXorProduct(a, b, n));
    }
}

This Python function iterates over all possible x values using a range and calculates the maximum XOR product with the modulo operation. This is a direct implementation that calculates all possible outcomes.

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.

def optimized_max_xor_product(a, b, n):
    MOD = 1000000007
    max_product = 0
    for i in range(n):
        x = (1 << n) - 1 - (1 << i)
        xor_a = a ^ x
        xor_b = b ^ x
        prod = (xor_a * xor_b) % MOD
        max_product = max(max_product, prod)
    return max_product

# Example Usage
print(optimized_max_xor_product(6, 7, 5))
public class MaxXorProductOptimized {
    private static final int MOD = 1000000007;

    public static long optimizedMaxXorProduct(int a, int b, int n) {
        long maxProduct = 0;
        for (int i = 0; i < n; ++i) {
            int x = (1 << n) - 1 - (1 << i);
            long xorA = a ^ x;
            long xorB = b ^ x;
            long prod = (xorA * xorB) % MOD;
            maxProduct = Math.max(maxProduct, prod);
        }
        return maxProduct;
    }

    public static void main(String[] args) {
        int a = 6, b = 7, n = 5;
        System.out.println(optimizedMaxXorProduct(a, b, n));
    }
}
#include <iostream>
#define MOD 1000000007

using namespace std;

long long optimizedMaxXorProduct(int a, int b, int n) {
    long long maxProduct = 0;
    for (int i = 0; i < n; ++i) {
        int x = (1 << n) - 1 - (1 << i);
        long long xorA = a ^ x;
        long long xorB = b ^ x;
        long long prod = (xorA * xorB) % MOD;
        maxProduct = max(maxProduct, prod);
    }
    return maxProduct;
}

int main() {
    int a = 6, b = 7, n = 5;
    cout << optimizedMaxXorProduct(a, b, n) << endl;
    return 0;
}
function optimizedMaxXorProduct(a, b, n) {
    const MOD = 1000000007;
    let maxProduct = 0;
    for (let i = 0; i < n; i++) {
        let x = (1 << n) - 1 - (1 << i);
        let xorA = a ^ x;
        let xorB = b ^ x;
        let prod = (xorA * xorB) % MOD;
        maxProduct = Math.max(maxProduct, prod);
    }
    return maxProduct;
}

console.log(optimizedMaxXorProduct(6, 7, 5));
#include <stdio.h>
#define MOD 1000000007

long long optimizedMaxXorProduct(int a, int b, int n) {
    long long maxProduct = 0;
    for (int i = 0; i < n; ++i) {
        int x = (1 << n) - 1 - (1 << i);
        long long xorA = a ^ x;
        long long xorB = b ^ x;
        long long prod = (xorA * xorB) % MOD;
        if (prod > maxProduct) {
            maxProduct = prod;
        }
    }
    return maxProduct;
}

int main() {
    int a = 6, b = 7, n = 5;
    printf("%lld\n", optimizedMaxXorProduct(a, b, n));
    return 0;
}
using System;

public class MaxXorProductOptimized {
    private const int MOD = 1000000007;

    public static long OptimizedMaxXorProduct(int a, int b, int n) {
        long maxProduct = 0;
        for (int i = 0; i < n; ++i) {
            int x = (1 << n) - 1 - (1 << i);
            long xorA = a ^ x;
            long xorB = b ^ x;
            long prod = (xorA * xorB) % MOD;
            if (prod > maxProduct) maxProduct = prod;
        }
        return maxProduct;
    }

    public static void Main() {
        int a = 6, b = 7, n = 5;
        Console.WriteLine(OptimizedMaxXorProduct(a, b, n));
    }
}

This Python function leverages strategically selecting x by modifying pertinent bits only. It curbs unnecessary computation by pinpointing influential XOR factors directly impacting the maximum product.

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).

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);
}
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)
}
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–

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

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.

Comments

Next problem · similarMaximum XOR After Operations Medium
Now write it yourselfClose this page and solve Maximum Xor Product in the editor, without looking.
Practise Maximum Xor Product