Maximum XOR After Operations solution and explanation
5 more videos on this problem
Leetcode BiWeekly contest 81 - Medium - Maximum XOR After OperationsPrakhar Agrawal · 11:20 · 2K views
花花酱 LeetCode 2317. Maximum XOR After Operations - 刷题找工作 EP398Hua Hua · 13:11 · 1K views
2317. Maximum XOR After Operations (Leetcode Medium)Programming Live with Larry · 10:19 · 1K views
BiWeekly Contest 81 | 6105. Maximum XOR After OperationscodingMohan · 13:42 · 1K views
Maximum XOR After Operations - LeetCode 2317 - Java Solutionalgobest - Computer Science · 2:32 · 415 views
Leetcode 2317. Maximum XOR After Operations - check bits for 1, i.e., bitwise or operationsCode-Yao · 10:31 · 300 views
The problem
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 <= 1050 <= 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.
def maximumXOR(nums):
max_xor = 0
for num in nums:
max_xor |= num
return max_xor
nums = [3, 2, 4, 6]
print(maximumXOR(nums)) # Output: 7public class MaximumXOR {
public static int maximumXOR(int[] nums) {
int maxXor = 0;
for (int num : nums) {
maxXor |= num;
}
return maxXor;
}
public static void main(String[] args) {
int[] nums = {3, 2, 4, 6};
System.out.println(maximumXOR(nums)); // Output: 7
}
}#include <iostream>
#include <vector>
int maximumXOR(std::vector<int>& nums) {
int max_xor = 0;
for (int num : nums) {
max_xor |= num;
}
return max_xor;
}
int main() {
std::vector<int> nums = {3, 2, 4, 6};
std::cout << maximumXOR(nums) << std::endl;
return 0;
}function maximumXOR(nums) {
let maxXor = 0;
nums.forEach(num => {
maxXor |= num;
});
return maxXor;
}
const nums = [3, 2, 4, 6];
console.log(maximumXOR(nums)); // Output: 7#include <stdio.h>
int maximumXOR(int* nums, int numsSize) {
int max_xor = 0;
for (int i = 0; i < numsSize; ++i) {
max_xor |= nums[i];
}
return max_xor;
}
int main() {
int nums[] = {3, 2, 4, 6};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maximumXOR(nums, numsSize));
return 0;
}using System;
class Program {
public static int MaximumXOR(int[] nums) {
int maxXor = 0;
foreach (int num in nums) {
maxXor |= num;
}
return maxXor;
}
static void Main() {
int[] nums = {3, 2, 4, 6};
Console.WriteLine(MaximumXOR(nums)); // Output: 7
}
}Python makes operation simple with its flexible lists and direct '|' operator, making array operations very intuitive. Accumulating OR of elements yields maximum XOR.
Time Complexity: O(n)
Space Complexity: O(1)
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).
def maximumXOR(nums):
result = 0
for num in nums:
if (result & num) == 0:
result |= num
return result
nums = [3, 2, 4, 6]
print(maximumXOR(nums)) # Output: 7public class MaximumXOR {
public static int maximumXOR(int[] nums) {
int result = 0;
for (int num : nums) {
if ((result & num) == 0) {
result |= num;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {3, 2, 4, 6};
System.out.println(maximumXOR(nums)); // Output: 7
}
}#include <iostream>
#include <vector>
int maximumXOR(std::vector<int>& nums) {
int result = 0;
for(int num : nums) {
if ((result & num) == 0) {
result |= num;
}
}
return result;
}
int main() {
std::vector<int> nums = {3, 2, 4, 6};
std::cout << maximumXOR(nums) << std::endl;
return 0;
}function maximumXOR(nums) {
let result = 0;
for (let num of nums) {
if ((result & num) === 0) {
result |= num;
}
}
return result;
}
const nums = [3, 2, 4, 6];
console.log(maximumXOR(nums)); // Output: 7#include <stdio.h>
int maximumXOR(int* nums, int numsSize) {
int result = 0;
for (int i = 0; i < numsSize; ++i) {
if (!(result & nums[i])) {
result |= nums[i];
}
}
return result;
}
int main() {
int nums[] = {3, 2, 4, 6};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maximumXOR(nums, numsSize));
return 0;
}using System;
class Program {
public static int MaximumXOR(int[] nums) {
int result = 0;
foreach (int num in nums) {
if ((result & num) == 0) {
result |= num;
}
}
return result;
}
static void Main() {
int[] nums = {3, 2, 4, 6};
Console.WriteLine(MaximumXOR(nums)); // Output: 7
}
}This Python implementation efficiently produces the optimum XOR value by determining and accumulating additional sub-elements of the numbers list via logical exclusions, transforming merely clear elements into a maximal mixing bet on their positions.
Time Complexity: O(n)
Space Complexity: O(1)
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).
function maximumXOR(nums: number[]): number {
let ans = 0;
for (const x of nums) {
ans |= x;
}
return ans;
}func maximumXOR(nums []int) (ans int) {
for _, x := range nums {
ans |= x
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Optimize Using XOR Properties | Time Complexity: O(n) |
| Approach 2: Try Maintaining Highest Bit | Time Complexity: O(n) |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Optimize Using XOR Properties | O(n) | O(1) | Best general solution; uses insight that final XOR equals OR of all elements |
| Maintain Highest Bit | O(n) | O(1) | Useful when reasoning about bit positions individually during interviews |
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.