Skip to main content
Talentd

Maximum XOR After Operations - Solution & Explanation

MediumArrayMathBit Manipulation16 min readAsked at: Amazon, American Express
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums. In one operation, select any non-negative integer x and an index i, then update nums[i] to be equal to nums[i] AND (nums[i] XOR x).

Note that AND is the bitwise AND operation and XOR is the bitwise XOR operation.

Return the maximum possible bitwise XOR of all elements of nums after applying the operation any number of times.

 

Example 1:

Input: nums = [3,2,4,6]
Output: 7
Explanation: Apply the operation with x = 4 and i = 3, num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2.
Now, nums = [3, 2, 4, 2] and the bitwise XOR of all the elements = 3 XOR 2 XOR 4 XOR 2 = 7.
It can be shown that 7 is the maximum possible bitwise XOR.
Note that other operations may be used to achieve a bitwise XOR of 7.

Example 2:

Input: nums = [1,2,3,9,2]
Output: 11
Explanation: Apply the operation zero times.
The bitwise XOR of all the elements = 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11.
It can be shown that 11 is the maximum possible bitwise XOR.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 108

Approach Overview

Problem Overview: You can repeatedly choose two indices i and j and replace nums[i] with nums[i] & nums[j]. After any number of operations, compute the maximum possible XOR of all elements in the array. The challenge is understanding how the AND operation changes individual bits and how that affects the final XOR.

Approach 1: Optimize Using XOR Properties (O(n) time, O(1) space)

The key observation is that the operation a = a & b can only turn bits off, never on. However, you can strategically apply operations so that a chosen bit survives in exactly one element, ensuring it contributes to the final XOR. If any number in the array contains a specific bit, you can preserve that bit in one position while clearing it from others using repeated AND operations. This means every bit that appears in the array can be made to appear exactly once in the final XOR result. Because XOR of a bit appearing once is 1, the maximum XOR equals the bitwise OR of all numbers. The algorithm simply iterates through the array and accumulates result |= num. This approach relies on understanding properties of Bit Manipulation and how XOR behaves when bits appear an odd number of times.

Approach 2: Try Maintaining Highest Bit (O(n) time, O(1) space)

Another way to reason about the problem is by analyzing bits from highest to lowest. For each bit position, check whether at least one element contains that bit. If it exists anywhere in the array, you can maintain that bit in one number while clearing it from others through AND operations. This guarantees the bit contributes to the final XOR. Effectively, this approach builds the answer bit by bit by scanning the array and checking whether each bit can survive the sequence of operations. The final value becomes the union of all bits seen in the array, which again equals the bitwise OR of all elements. This reasoning approach is helpful when practicing problems involving Array traversal and Math-based bit reasoning.

Recommended for interviews: The XOR‑property insight is what interviewers typically expect. Showing the bit-level reasoning—why any existing bit can be preserved exactly once—demonstrates strong understanding of XOR and AND interactions. A brute-force simulation of operations would be infeasible, so recognizing the OR reduction quickly signals solid bit manipulation skills.

Approach 1: Approach 1: Optimize Using XOR Properties

By carefully observing the problem, we notice that the operation simplifies each element of the array such that its bitwise representation tends to be adjusted to involve clearing some of its high bits. Interestingly, for each number, the operation can reduce it but can't increase it. Therefore, the maximum possible XOR is achieved by finding the bitwise OR of all numbers in the array. Subsequently, the maximum XOR becomes equivalent to its OR.

This solution calculates the OR of all elements because OR is a good approximation for the maximum XOR result. Thus, iterating through the array and accumulating the OR in variable 'max_xor' provides the desired result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Approach 2: Try Maintaining Highest Bit

Here's an alternative perspective: as you experiment, note that the bend towards using the OR function comes from aiming to maintain the highest significant bit set afterward. For accuracy, you intend to simulate the result such that the most significant bits untouched under AND, deliver the most powerful bit (akin to achieving the pinnacle of XOR).

The solution follows a stringent approach where it iteratively attempts to accumulate bits that weren't part of the currently achieved number using OR, adjusting for conflict scenarios under very particular AND operations.

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: Bit Manipulation

In one operation, we can update nums[i] to nums[i] AND (nums[i] XOR x). Since x is any non-negative integer, the result of nums[i] \oplus x can be any value. By performing a bitwise AND operation with nums[i], we can change some of the 1 bits in the binary representation of nums[i] to 0.

The problem requires us to find the maximum bitwise XOR sum of all elements in nums. For a binary bit, as long as there is an element in nums with the corresponding binary bit set to 1, the contribution of this binary bit to the maximum bitwise XOR sum is 1. Therefore, the answer is the result of the bitwise OR operation of all elements in nums.

The time complexity is O(n), where n is the length of nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Optimize Using XOR Properties

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1)

Approach 2: Try Maintaining Highest Bit

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

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Optimize Using XOR PropertiesO(n)O(1)Best general solution; uses insight that final XOR equals OR of all elements
Maintain Highest BitO(n)O(1)Useful when reasoning about bit positions individually during interviews

Video Solution

Leetcode BiWeekly contest 81 - Medium - Maximum XOR After Operations • Prakhar Agrawal • 2,232 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Maximum XOR After Operations easy or hard?
The problem is rated Medium because the optimal solution depends on recognizing a non-obvious bit manipulation property. Implementation is simple once the insight is known, but discovering that the answer equals the OR of all elements requires strong XOR reasoning.
Maximum XOR After Operations Python/Java solution
Both Python and Java implementations follow the same idea: iterate through the array and accumulate the OR of all numbers. In Python use result |= num inside a loop, and in Java use result |= num with an integer accumulator. The logic is identical across languages.
How to solve Maximum XOR After Operations in O(n)?
Traverse the array and compute the bitwise OR of all elements using result |= num. This works because any bit present in the array can be preserved in exactly one element after performing AND operations on others. The resulting XOR becomes equal to the OR of all numbers.
Is Maximum XOR After Operations asked at Google/Amazon/Meta?
Problems involving XOR properties and bit manipulation frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying concepts—bitwise operations, XOR behavior, and greedy bit reasoning—are common interview topics.
What is the best approach for Maximum XOR After Operations ?
The optimal approach uses a bit manipulation insight: the maximum possible XOR equals the bitwise OR of all elements in the array. Since the operation nums[i] = nums[i] & nums[j] can only remove bits, you can preserve any existing bit in exactly one number. Iterating through the array and computing the OR of all values produces the answer in O(n) time and O(1) space.
What data structure is used in Maximum XOR After Operations ?
The solution mainly uses array traversal and bitwise operations. No complex data structures are required; a single integer variable accumulates the bitwise OR while iterating through the array.
What is the time complexity of Maximum XOR After Operations ?
The optimal solution runs in O(n) time because it scans the array once to compute the bitwise OR of all numbers. Space complexity is O(1) since only a single accumulator variable is needed. No additional data structures are required.

Ready to solve this problem?

Practice Maximum XOR After Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum XOR of Two Numbers in an Array

Next

Maximum Xor Product