Abstract / Summary

Given two arrays, find the pair whose product xor value is the largest.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 30% (50k+ submissions).

Typical patterns to solve this problem:

• Bit Manipulation
• Greedy
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a single method maximumXorProduct that receives three integers a, b, and n. Its purpose is to iteratively examine each bit position from 0 up to n-1, optionally flipping the corresponding bits in both a and b. After each potential flip, the method evaluates whether the product of the modified numbers exceeds the current product. If the product improves, the flipped values replace the originals. At the end of the loop the method returns the product modulo 1_000_000_007. The algorithm relies on bitwise XOR to toggle bits and on integer multiplication to compare candidate products.

Core Logic

The loop that drives the transformation is the heart of the solution. It iterates over every bit position within the range defined by n.

for pos in range(n):
    mask = 1 << pos

The mask variable isolates a single bit by left-shifting 1 to the current position. This mask is then used to generate two candidate numbers where the targeted bit is flipped in both a and b.

aa = a ^ mask
bb = b ^ mask

The XOR operation toggles the bit: if the bit was 0 it becomes 1, and if it was 1 it becomes 0. The method then decides whether adopting these flipped values yields a larger product.

if a * b < aa * bb:
    a = aa
    b = bb

Only when the product of the candidates strictly exceeds the current product does the algorithm commit to the change. This “greedy” step ensures that each iteration either improves the result or leaves the numbers unchanged.

Finally, the method returns the product reduced modulo a large prime, which is a common technique to keep the result within 32-bit integer limits.

return (a * b) % 1_000_000_007

Edge Cases Handled

When n is zero the range(n) sequence is empty, so the loop body never executes. In that situation the method directly returns the original product modulo the prime, correctly handling the case where no bits are available for flipping.

If either a or b is initially zero, the product starts at zero. The XOR operation may turn a zero into a non-zero value if the corresponding bit in the mask is set, allowing the product to become positive. The conditional check a * b < aa * bb captures this transition, ensuring that a beneficial flip is accepted.

The algorithm also gracefully handles the scenario where flipping a bit would reduce the product. Because the comparison uses a strict <, any non-improving flip is ignored, leaving the numbers unchanged. This behavior naturally accommodates cases where the bits being toggled are already set to the optimal configuration for maximizing the product.

When n exceeds the bit-length of the input numbers, the mask will eventually target bits beyond the most significant set bit. Flipping such higher bits introduces large values, but the conditional check still guarantees that only flips that increase the product are retained. Thus the method safely processes any non-negative n without overflow concerns, relying on Python’s arbitrary-precision integers.

Performance Considerations

The implementation leverages bitwise operations (<< and ^) which execute in constant time on typical hardware. By constructing the mask once per iteration and reusing it for both numbers, the code avoids redundant calculations. The multiplication used for comparison is performed only twice per loop iteration, and the conditional guard prevents unnecessary assignments.

Because the loop runs exactly n times, the algorithm’s runtime scales linearly with the number of examined bit positions. The use of a single mutable pair of variables (a and b) eliminates the need for auxiliary data structures, keeping memory usage minimal. The final modulo operation is performed a single time after the loop, avoiding repeated reductions that could add overhead.

Overall, the code exhibits a tight inner loop with low-overhead operations, making it well-suited for scenarios where n can be large but still within practical limits for a linear scan.

Imagine two numbers, a and b, that are hiding secrets behind what we call bits. Bits are like tiny light switches that can be either on or off, just like a lamp in a bedroom. There are n different switches we can play with.

The code goes through each switch one by one, starting from the very first one and moving along. For every switch, a special thing happens. The code creates a mask, which is a tool to reach out and touch that specific switch. By using the caret symbol, it flips the switch. Turning a switch on makes it off, and turning it off makes it on.

After flipping the switch, the code does a quick check. It multiplies a and b together to see how big the result is. Then, it compares that result to the new, swapped version. If the new numbers made a larger result than the old ones, it decides to keep the new version. This continues until every single one of the n switches has been checked and adjusted to make the final result as big as it can possibly be.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python	TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java	Go	Python	TS
	Progiez	C++		Java		Python
github	charles-wangkai			Java
	everthis		JS
	fsq	C++
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality