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 operationany number of times.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5

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 <= 10^5
  • 0 <= nums[i] <= 10^8

Solution

Method 1 – Bitwise OR of All Elements

Intuition

The operation allows us to clear any bit in any element, but we cannot set a bit that was not present in any element. Thus, the maximum possible XOR is achieved by taking the bitwise OR of all elements, as we can always clear bits to match the OR pattern.

Approach

  1. Initialize ans to 0.
  2. For each number in nums, perform ans |= num.
  3. Return ans as the maximum possible XOR after any number of operations.

Complexity

  • ⏰ Time complexity: O(n) — Each element is processed once.
  • 🧺 Space complexity: O(1) — Only a variable for the result.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    int maximumXOR(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) ans |= x;
        return ans;
    }
};
1
2
3
4
5

func maximumXOR(nums []int) int {
    ans := 0
    for _, x := range nums { ans |= x }
    return ans
}
1
2
3
4
5
6
7

class Solution {
    public int maximumXOR(int[] nums) {
        int ans = 0;
        for (int x : nums) ans |= x;
        return ans;
    }
}
1
2
3
4
5
6
7

class Solution {
    fun maximumXOR(nums: IntArray): Int {
        var ans = 0
        for (x in nums) ans = ans or x
        return ans
    }
}
1
2
3
4
5

def maximum_xor(nums: list[int]) -> int:
    ans = 0
    for x in nums:
        ans |= x
    return ans
1
2
3
4
5

impl Solution {
    pub fn maximum_xor(nums: Vec<i32>) -> i32 {
        nums.into_iter().fold(0, |ans, x| ans | x)
    }
}
1
2
3
4
5
6
7

class Solution {
    maximumXOR(nums: number[]): number {
        let ans = 0
        for (const x of nums) ans |= x
        return ans
    }
}