LeetCode 2317 - Maximum XOR After Operations

The problem gives us an integer array nums, and we may perform a special operation any number of times. In one operation, we choose an index i and any non-negative integer x, then replace: Our goal is to maximize the bitwise XOR of all elements in the array after performing as…

leetcodemediumarraymathbit-manipulation

LeetCode Problem 2317

Difficulty: 🟡 Medium
Topics: Array, Math, Bit Manipulation

Solution

Problem Understanding

The problem gives us an integer array nums, and we may perform a special operation any number of times. In one operation, we choose an index i and any non-negative integer x, then replace:

nums[i] = nums[i] AND (nums[i] XOR x)

Our goal is to maximize the bitwise XOR of all elements in the array after performing as many operations as we want.

The key challenge is understanding what this operation actually allows us to do to each number. At first glance, the expression looks complicated because it combines both XOR and AND. However, once we analyze the bit behavior carefully, the problem becomes much simpler.

The input size can be very large:

  • nums.length can be up to 10^5
  • Each number can be as large as 10^8

These constraints immediately rule out any brute-force simulation of operations. Since there are infinitely many choices for x, trying all operations directly is impossible. We need to derive a mathematical property of the operation instead.

An important observation is that the operation only removes bits from a number, it never creates new 1 bits. Therefore, every number can only lose bits over time.

Some important edge cases include:

  • Arrays containing only zeros
  • Arrays with a single element
  • Numbers with completely disjoint bit patterns
  • Numbers sharing many overlapping bits
  • Very large arrays where efficiency matters

The problem guarantees all numbers are non-negative, so we only deal with standard binary bit manipulation without worrying about sign bits.

Approaches

Brute Force Approach

A brute-force strategy would attempt to simulate operations on the array. For every index, we could try many possible values of x, generate new array states, compute the resulting XOR, and search for the maximum possible answer.

This approach is theoretically correct because it explores reachable states. However, it is completely impractical.

The problem is that:

  • x can be any non-negative integer
  • The number of possible operations is enormous
  • The state space grows exponentially
  • Arrays can contain up to 100000 elements

Even for very small arrays, exhaustive exploration becomes infeasible.

The brute-force approach fails because the operation space is effectively infinite.

Optimal Approach

The key insight comes from analyzing the operation bit by bit.

Consider a single bit position in nums[i].

If a bit in nums[i] is already 0, the result after the operation will always remain 0.

If a bit in nums[i] is 1, then:

  • We can choose x so that (nums[i] XOR x) has either 0 or 1 at that position
  • Since the final operation is an AND with the original bit 1, we can keep the bit as 1 or turn it into 0

Therefore, the operation allows us to independently remove any set bit from a number.

This means each number can be transformed into any subset of its original bits.

Now consider the final XOR.

A bit position can appear in the final XOR if at least one number originally contains that bit. Since we can selectively remove bits from numbers, we can always arrange for a bit to contribute to the final XOR whenever it exists somewhere in the array.

That means the maximum possible XOR simply contains every bit that appears in at least one number.

This is exactly the bitwise OR of all elements.

So the answer is:

nums[0] OR nums[1] OR nums[2] OR ...

This transforms the problem into a simple linear scan.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Explores operation states, infeasible
Optimal O(n) O(1) Compute bitwise OR of all elements

Algorithm Walkthrough

  1. Initialize a variable called result to 0.

This variable will accumulate every bit that appears anywhere in the array. 2. Iterate through each number in nums.

For every number, combine it with result using bitwise OR. 3. Update:

result = result OR current_number

The OR operation ensures that every bit appearing in any element becomes part of the final answer. 4. Continue until all elements have been processed. 5. Return result.

This value represents the maximum achievable XOR after any number of operations.

Why it works

The operation allows us to remove bits from individual numbers but never add new bits. Therefore, a bit can only appear in the final XOR if that bit existed in at least one original number.

Since we can selectively preserve bits to make their XOR contribution odd, every existing bit can be made to appear in the final XOR. Thus, the maximum achievable XOR contains all bits that appear anywhere in the array, which is exactly the bitwise OR of all numbers.

Python Solution

from typing import List

class Solution:
    def maximumXOR(self, nums: List[int]) -> int:
        result = 0
        
        for num in nums:
            result |= num
        
        return result

The implementation is extremely concise because the mathematical observation eliminates the need for simulation.

The variable result starts at 0. As we iterate through the array, we continuously apply the bitwise OR operator.

The expression:

result |= num

is shorthand for:

result = result | num

This accumulates every bit that appears in any number.

At the end of the loop, result contains the union of all set bits across the array, which is the maximum achievable XOR.

Go Solution

func maximumXOR(nums []int) int {
    result := 0

    for _, num := range nums {
        result |= num
    }

    return result
}

The Go implementation follows exactly the same logic as the Python version.

Go uses the |= operator for bitwise OR assignment, just like Python.

Since the constraints fit comfortably within Go's int type, there are no overflow concerns. The solution also uses constant extra memory because only a single accumulator variable is maintained.

Worked Examples

Example 1

Input:

nums = [3,2,4,6]

Binary representations:

Number Binary
3 011
2 010
4 100
6 110

We compute the cumulative OR step by step.

Step Current Number Result Before Result After
1 3 (011) 000 011
2 2 (010) 011 011
3 4 (100) 011 111
4 6 (110) 111 111

Final result:

111 binary = 7

Answer:

7

Example 2

Input:

nums = [1,2,3,9,2]

Binary representations:

Number Binary
1 0001
2 0010
3 0011
9 1001
2 0010

Cumulative OR process:

Step Current Number Result Before Result After
1 1 0000 0001
2 2 0001 0011
3 3 0011 0011
4 9 0011 1011
5 2 1011 1011

Final binary value:

1011 binary = 11

Answer:

11

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed exactly once
Space O(1) Only one accumulator variable is used

The algorithm performs a single pass through the array. Each iteration executes one constant-time bitwise OR operation.

No additional data structures proportional to input size are allocated, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def maximumXOR(self, nums: List[int]) -> int:
        result = 0
        
        for num in nums:
            result |= num
        
        return result

solution = Solution()

assert solution.maximumXOR([3, 2, 4, 6]) == 7          # provided example
assert solution.maximumXOR([1, 2, 3, 9, 2]) == 11      # provided example

assert solution.maximumXOR([0]) == 0                   # single zero
assert solution.maximumXOR([5]) == 5                   # single element
assert solution.maximumXOR([0, 0, 0]) == 0             # all zeros

assert solution.maximumXOR([1, 2, 4, 8]) == 15         # disjoint bits
assert solution.maximumXOR([7, 7, 7]) == 7             # identical numbers
assert solution.maximumXOR([1, 1, 1, 1]) == 1          # repeated single bit

assert solution.maximumXOR([8, 1]) == 9                # separated high and low bits
assert solution.maximumXOR([10, 5]) == 15              # complementary bits

assert solution.maximumXOR([100000000]) == 100000000   # large value
assert solution.maximumXOR([0, 100000000]) == 100000000 # zero plus large value

assert solution.maximumXOR([6, 10, 15]) == 15          # overlapping bits
Test Why
[3,2,4,6] Verifies provided example
[1,2,3,9,2] Verifies second example
[0] Smallest possible value
[5] Single-element array
[0,0,0] All bits absent
[1,2,4,8] Every number contributes unique bits
[7,7,7] Repeated identical values
[1,1,1,1] Duplicate single-bit numbers
[8,1] Combines distant bit positions
[10,5] Complementary bit patterns
[100000000] Large integer boundary
[0,100000000] Large value with zero
[6,10,15] Heavy bit overlap

Edge Cases

One important edge case is an array containing only zeros. Since no number contains any set bits, the bitwise OR remains zero. A buggy implementation might incorrectly assume operations can create new bits, but the operation only removes bits. The implementation handles this naturally because OR-ing zeros always produces zero.

Another important case is a single-element array. Since the final XOR equals the single remaining value, the maximum achievable answer is simply the original number itself. The algorithm works correctly because the OR of one number is that number.

A third important edge case involves overlapping bit patterns, such as [7, 7, 7]. Multiple numbers may share the same bits, but the maximum achievable XOR still only includes each bit once. The OR operation naturally captures this behavior without double counting bits.

A final important case is when different numbers contribute entirely different bits, such as [1, 2, 4, 8]. In this situation, every bit position can appear in the final answer simultaneously. The algorithm correctly combines all bits into the maximum value 15.