LeetCode 2527 - Find Xor-Beauty of Array

LeetCode Problem 2527

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

Solution

Problem Understanding

The problem defines a special value called the "effective value" for every possible triplet of indices (i, j, k) in the array:

$$((nums[i] \mid nums[j]) & nums[k])$$

where:

• | is the bitwise OR operator
• & is the bitwise AND operator

The xor-beauty of the array is the XOR of the effective values for all possible triplets.

The straightforward interpretation is that for an array of size n, we must evaluate:

$$\bigoplus_{i=0}^{n-1} \bigoplus_{j=0}^{n-1} \bigoplus_{k=0}^{n-1} ((nums[i] \mid nums[j]) & nums[k])$$

The challenge comes from the number of triplets. Since every index can independently take any value from 0 to n - 1, there are:

$$n^3$$

triplets in total.

The constraints allow:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

This immediately tells us that any cubic solution is impossible. Even a quadratic solution would be far too slow for the largest input sizes. We need something close to linear time.

The key to solving this problem is recognizing that bitwise operations often simplify when combined with XOR over many repeated combinations. Instead of evaluating every triplet directly, we need to derive a mathematical simplification.

An important observation is that XOR has cancellation properties:

$$x \oplus x = 0$$

and

$$x \oplus 0 = x$$

This means values appearing an even number of times disappear entirely from the final XOR.

Edge cases that matter include:

• Arrays with a single element
• Arrays where all elements are identical
• Arrays containing powers of two
• Large arrays where brute force is impossible
• Cases where many triplets produce repeated values that cancel under XOR

The problem guarantees that the array is non-empty and all numbers are positive integers, so we never need to handle empty input or negative values. The problem defines a function over all ordered triplets of indices $(i, j, k)$ in a 0-indexed array nums. For each triplet, we compute an “effective value” given by:

$$((nums[i] ;|; nums[j]) ;&; nums[k])$$

We then take the XOR of these effective values over all possible triplets, including those where indices repeat. The task is to compute this final XOR result efficiently.

In simpler terms, every element can be chosen independently for each position in the triplet, so we are effectively aggregating a large number of bitwise expressions. The output is the XOR of all such results.

The constraints are large: $n$ can be up to $10^5$, and values up to $10^9$. This immediately rules out any cubic or even quadratic enumeration of triplets. A naive approach would involve $O(n^3)$ computations, which is infeasible.

Important edge cases include arrays of size 1, where all triplets are identical, arrays with all identical elements, and arrays containing zeros, which often simplify bitwise expressions but can still mislead brute-force reasoning. The key guarantee is that all triplets are allowed, including repeated indices.

Approaches

Brute Force Approach

The most direct solution is to generate every possible triplet (i, j, k).

For each triplet:

1. Compute (nums[i] | nums[j])
2. Compute ((nums[i] | nums[j]) & nums[k])
3. XOR this value into the answer

This works because it exactly follows the problem definition.

However, there are n^3 triplets. With n = 10^5, this becomes completely infeasible.

Even for n = 1000, we would already have:

$$1000^3 = 10^9$$

operations, which is far beyond acceptable limits.

Key Insight

The crucial observation is that the entire expression simplifies dramatically.

The xor-beauty is actually equal to the XOR of all numbers in the array.

In other words:

$$\text{xor-beauty} = nums[0] \oplus nums[1] \oplus \cdots \oplus nums[n-1]$$

To understand why, we analyze the expression bit by bit.

Consider a single bit position independently. A bit contributes to the final XOR only if it appears an odd number of times across all effective values.

For a particular bit:

$$((a \mid b) & c)$$

produces 1 only when:

• c has that bit set
• at least one of a or b has that bit set

When counting all triplets, every combination that appears an even number of times cancels out under XOR.

After simplifying the parity contributions, the only surviving contribution is exactly the XOR of all elements in the array.

This transforms the problem from a complex triplet enumeration problem into a simple linear XOR accumulation.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Evaluates every possible triplet directly
Optimal	O(n)	O(1)	Uses the mathematical simplification that xor-beauty equals XOR of all elements

Algorithm Walkthrough

Optimal Algorithm

1. Initialize a variable result to 0.

This variable will store the running XOR of all numbers. 2. Traverse the array from left to right.

For each number value in nums, update:

$$result = result \oplus value$$

XOR accumulation works because XOR is associative and commutative. 3. After processing all elements, return result.

Due to the mathematical property of the xor-beauty expression, this accumulated XOR is exactly the final answer.

Why it works

The proof relies on parity cancellation in XOR operations.

Each bit position behaves independently. When counting contributions from all triplets, any bit contribution appearing an even number of times cancels out entirely. After analyzing the combinations generated by:

$$((nums[i] \mid nums[j]) & nums[k])$$

the only remaining odd-parity contributions correspond exactly to the bits appearing in the XOR of all array elements.

Therefore:

$$\bigoplus_{i,j,k} ((nums[i] \mid nums[j]) & nums[k]) = \bigoplus_{x \in nums} x$$ The brute-force solution iterates over all triplets $(i, j, k)$, computes (nums[i] | nums[j]) & nums[k], and XORs the result into an accumulator. This is correct by definition because it directly follows the problem statement.

However, this approach is computationally infeasible because it requires iterating over $n^3$ triplets. With $n = 10^5$, this would be astronomically large.

Key Insight for Optimization

The critical observation is that the bitwise structure allows us to separate computation by individual bits.

For a single bit position, we analyze when the bit contributes to the final XOR. The expression:

((a ;|; b) ;&; c)

has a bit set at position $b$ if and only if:

• $c$ has that bit set
• at least one of $a$ or $b$ has that bit set

So for a fixed bit, we are effectively counting how many triplets produce a 1 at that bit position. The XOR over all triplets depends only on whether this count is odd or even.

A deeper simplification reveals a powerful fact: each element contributes independently to the final XOR-beauty, and the pairwise OR over all triplets collapses such that the final answer is simply:

$$nums[0] ; \oplus ; nums[1] ; \oplus ; \dots ; \oplus ; nums[n-1]$$

This works because every bit that appears in any number of triplets ends up being counted an even number of times except those corresponding to the XOR of all elements.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Direct enumeration of all triplets
Optimal	O(n)	O(1)	Reduce to XOR of all elements using bitwise symmetry

Algorithm Walkthrough

1. Initialize a variable result to 0, which will store the cumulative XOR of all elements. This is based on the key insight that the final answer depends only on XOR aggregation of the array.
2. Iterate through each number in the array nums. For each element, update result using XOR: result ^= num. This step aggregates contributions of all elements into a single value.
3. After processing all elements, return result as the final xor-beauty of the array.

The reason we do not explicitly compute triplets is that their combined XOR contribution simplifies due to cancellation properties of XOR over repeated structured combinations. Each element effectively contributes its value an odd or even number of times across all valid triplets, and the final parity reduces exactly to a simple XOR of all elements.

Why it works

The XOR operation is linear over parity of occurrences. In the full expansion of all triplets, each nums[i] contributes to the final XOR in a way that depends only on the parity of how many times each bit is activated across all valid combinations. Due to symmetry in OR and AND across all index permutations, the net effect is that all higher-order interactions cancel out, leaving only the XOR of all elements.

Python Solution

from typing import List

class Solution:
    def xorBeauty(self, nums: List[int]) -> int:
        result = 0

        for value in nums:
            result ^= value

        return result

The implementation is intentionally simple because the mathematical reduction eliminates the need for any complex logic.

The variable result starts at 0, which is the identity element for XOR.

As we iterate through the array, each value is XORed into result. XOR accumulation naturally combines all elements into a single final value.

The loop runs once per element, giving linear time complexity.

No auxiliary data structures are required, so the solution uses constant extra space. for num in nums: result ^= num return result

The implementation directly applies the derived simplification. The loop accumulates the XOR of all elements, and the final result is returned. No additional data structures or nested loops are needed.

## Go Solution

```go
func xorBeauty(nums []int) int {
    result := 0

    for _, value := range nums {
        result ^= value
    }

    return result
}

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

Go uses the ^ operator for bitwise XOR. The range loop iterates through the slice efficiently.

Since the constraints guarantee values fit comfortably within standard integer ranges, no special overflow handling is necessary.

The solution uses only a single integer variable for accumulation, so the space complexity remains constant.

Worked Examples

Example 1

Input:

nums = [1, 4]

The optimal algorithm simply XORs all elements.

Step	Current Value	Running XOR
Start	-	0
1	1	0 ^ 1 = 1
2	4	1 ^ 4 = 5

Final answer:

5

This matches the exhaustive triplet computation from the problem statement.

Example 2

Input:

nums = [15,45,20,2,34,35,5,44,32,30]

Step-by-step XOR accumulation:

Step	Value	Running XOR
Start	-	0
1	15	15
2	45	34
3	20	54
4	2	52
5	34	22
6	35	53
7	5	48
8	44	28
9	32	60
10	30	34

Final answer:

34

Complexity Analysis

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

The algorithm performs one XOR operation per element in the array. Since XOR is a constant-time operation, the total runtime grows linearly with the input size.

No additional arrays, maps, or auxiliary data structures are allocated, so the extra memory usage remains constant regardless of input size.

Test Cases

from typing import List

class Solution:
    def xorBeauty(self, nums: List[int]) -> int:
        result = 0

        for value in nums:
            result ^= value

        return result

sol = Solution()

assert sol.xorBeauty([1, 4]) == 5  # provided example
assert sol.xorBeauty([15,45,20,2,34,35,5,44,32,30]) == 34  # provided example

assert sol.xorBeauty([7]) == 7  # single element
assert sol.xorBeauty([1, 1]) == 0  # duplicate values cancel
assert sol.xorBeauty([2, 2, 2]) == 2  # odd count survives
assert sol.xorBeauty([8, 8, 8, 8]) == 0  # even count cancels

assert sol.xorBeauty([1, 2, 3]) == 0  # 1 ^ 2 ^ 3 = 0
assert sol.xorBeauty([5, 10, 15]) == 0  # multiple cancellations

assert sol.xorBeauty([1024, 2048, 4096]) == (1024 ^ 2048 ^ 4096)  # large powers of two
assert sol.xorBeauty([10**9]) == 10**9  # maximum value boundary

large_case = [1] * 100000
assert sol.xorBeauty(large_case) == 0  # stress test with even count

Test Case Summary

Test	Why
[1, 4]	Verifies the provided example
[15,45,20,2,34,35,5,44,32,30]	Verifies larger provided example
[7]	Tests single-element array
[1, 1]	Confirms XOR cancellation
[2, 2, 2]	Tests odd repetition
[8, 8, 8, 8]	Tests even repetition
[1, 2, 3]	Validates XOR collapsing to zero
[5, 10, 15]	Tests mixed values with cancellation
[1024, 2048, 4096]	Tests higher bit positions
[10**9]	Tests maximum value constraint
[1] * 100000	Stress test for maximum input size

Edge Cases

Single Element Array

If the array contains only one element, there is exactly one triplet:

$$(0,0,0)$$

The effective value becomes:

$$((x \mid x) & x) = x$$

So the xor-beauty equals the element itself. The implementation handles this naturally because XORing a single value with 0 simply returns that value.

All Elements Identical

Consider an array like:

[5, 5, 5, 5]

Since XOR cancels pairs:

$$5 \oplus 5 = 0$$

an even number of identical values disappears entirely. The implementation correctly accumulates XOR and automatically applies this cancellation behavior.

Maximum Input Size

A brute-force solution would completely fail for arrays of length 10^5 because it would require evaluating:

$$(10^5)^3 = 10^{15}$$

triplets.

The optimal solution processes each element exactly once, so it remains efficient even at the maximum constraint size.

Large Integer Values

The constraints allow values up to:

$$10^9$$

The algorithm uses only standard bitwise XOR operations, which are fully supported for these integer sizes in both Python and Go. No overflow issues occur because XOR does not increase magnitude beyond the bit width already present in the inputs.