# Find Xor-Beauty of Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-xor-beauty-of-array)
Canonical: https://scaleengineer.com/dsa/problems/find-xor-beauty-of-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** integer array `nums`.

The **effective value** of three indices `i`, `j`, and `k` is defined as `((nums[i] | nums[j]) & nums[k])`.

The **xor-beauty** of the array is the XORing of **the effective values of all the possible triplets** of indices `(i, j, k)` where `0 <= i, j, k < n`.

Return _the xor-beauty of_ `nums`.

**Note** that:

* `val1 | val2` is bitwise OR of `val1` and `val2`.
* `val1 & val2` is bitwise AND of `val1` and `val2`.

**Example 1:**

**Input:** nums = [1,4]
**Output:** 5
**Explanation:** 
The triplets and their corresponding effective values are listed below:
- (0,0,0) with effective value ((1 | 1) & 1) = 1
- (0,0,1) with effective value ((1 | 1) & 4) = 0
- (0,1,0) with effective value ((1 | 4) & 1) = 1
- (0,1,1) with effective value ((1 | 4) & 4) = 4
- (1,0,0) with effective value ((4 | 1) & 1) = 1
- (1,0,1) with effective value ((4 | 1) & 4) = 4
- (1,1,0) with effective value ((4 | 4) & 1) = 0
- (1,1,1) with effective value ((4 | 4) & 4) = 4 
Xor-beauty of array will be bitwise XOR of all beauties = 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5.

**Example 2:**

**Input:** nums = [15,45,20,2,34,35,5,44,32,30]
**Output:** 34
**Explanation:** `The xor-beauty of the given array is 34.`

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force Simulation
A straightforward approach that directly implements the problem description. It iterates through all n*n*n possible triplets of indices `(i, j, k)` and calculates the effective value for each. The xor-beauty is computed by XORing all these effective values together.
**Time:** O(n^3), where n is the number of elements in the `nums` array. This is because there are three nested loops, each running `n` times. · **Space:** O(1), as we only use a constant amount of extra space for loop counters and the result variable.
**Pros:** Simple to understand and implement directly from the problem statement.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (n up to 10^5).
### Explanation
This approach is a direct translation of the problem statement into code. We need to find the XOR sum of `((nums[i] | nums[j]) & nums[k])` for all possible combinations of indices `i`, `j`, and `k`.

```java
class Solution {
    public int xorBeauty(int[] nums) {
        int n = nums.length;
        int xorBeauty = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    int effectiveValue = (nums[i] | nums[j]) & nums[k];
                    xorBeauty ^= effectiveValue;
                }
            }
        }
        return xorBeauty;
    }
}
```
### Algorithm
*   Initialize a variable, `xorBeauty`, to 0. This will store the cumulative XOR sum.
*   Use a loop for index `i` from `0` to `n-1`, where `n` is the length of the `nums` array.
*   Inside this loop, nest another loop for index `j` from `0` to `n-1`.
*   Inside the second loop, nest a third loop for index `k` from `0` to `n-1`.
*   In the innermost loop, we have a valid triplet `(i, j, k)`. Calculate the effective value: `value = (nums[i] | nums[j]) & nums[k]`.
*   Update the `xorBeauty` by XORing it with the `value`: `xorBeauty ^= value`.
*   After the three loops have finished, `xorBeauty` will contain the XOR sum of all effective values, which is the desired result.

## Optimal Approach using Bitwise Properties
This approach leverages the properties of bitwise operations (XOR, OR, AND) to simplify the complex expression for xor-beauty. Instead of calculating the value for each of the `n^3` triplets, we can find a much simpler equivalent expression, which turns out to be the XOR sum of all elements in the array.
**Time:** O(n), where n is the number of elements in the `nums` array. We only need to iterate through the array once. · **Space:** O(1), as we only use a constant amount of extra space for the result variable.
**Pros:** Extremely efficient with a linear time complexity.; Simple to implement once the mathematical simplification is understood.; Easily passes the given constraints.
**Cons:** The derivation of the simplified formula is non-trivial and requires a good understanding of bitwise properties, making it less intuitive at first glance.
### Explanation
The xor-beauty is defined as the XOR sum of `((nums[i] | nums[j]) & nums[k])` over all possible triplets `(i, j, k)`. Let's denote this sum by `X`.
`X = ⨁_{0 <= i, j, k < n} ((nums[i] | nums[j]) & nums[k])`
The key to solving this problem efficiently is to simplify this expression using the properties of bitwise operations.
1.  **Distributive Property of AND over OR**: We know that `(a | b) & c = (a & c) | (b & c)`. Applying this to our term:
    `((nums[i] | nums[j]) & nums[k]) = (nums[i] & nums[k]) | (nums[j] & nums[k])`
2.  **Rewriting the Sum**: The total XOR sum can be rewritten by substituting this back:
    `X = ⨁_{i,j,k} [ (nums[i] & nums[k]) | (nums[j] & nums[k]) ]`
3.  **Simplifying the Inner Sums**: Let's fix `k` and analyze the sum over `i` and `j`. Let `a_p = nums[p] & nums[k]`. The sum for a fixed `k` is `S_k = ⨁_{i,j} (a_i | a_j)`.
    - In this sum, for any pair of distinct indices `p` and `q`, the term `(a_p | a_q)` appears, and so does `(a_q | a_p)`. Since `(a_p | a_q) = (a_q | a_p)`, their XOR is `(a_p | a_q) ^ (a_q | a_p) = 0`.
    - This means all terms where `i ≠ j` cancel each other out in pairs.
    - The only remaining terms are the "diagonal" ones where `i = j`: `S_k = ⨁_{i} (a_i | a_i) = ⨁_{i} a_i`.
4.  **Substituting Back**: Replacing `a_i` with its definition, we get `S_k = ⨁_{i} (nums[i] & nums[k])`.
5.  **Summing over k**: The total xor-beauty `X` is the XOR sum of all `S_k`:
    `X = ⨁_{k} S_k = ⨁_{k} [ ⨁_{i} (nums[i] & nums[k]) ]`
6.  **Swapping Summation Order**: The order of XORing doesn't matter, so we can swap the summations:
    `X = ⨁_{i} [ ⨁_{k} (nums[i] & nums[k]) ]`
7.  **Distributive Property of AND over XOR**: A less common but valid property is `a & (b ^ c) = (a & b) ^ (a & c)`. Applying this to the inner sum `⨁_{k} (nums[i] & nums[k])`, we get:
    `⨁_{k} (nums[i] & nums[k]) = nums[i] & (⨁_{k} nums[k])`
8.  **Final Simplification**: Let `XOR_ALL = ⨁_{p=0}^{n-1} nums[p]`. The expression for `X` becomes:
    `X = ⨁_{i} (nums[i] & XOR_ALL)`
    Applying the distributive property again:
    `X = (⨁_{i} nums[i]) & XOR_ALL`
    Substituting the definition of `XOR_ALL`:
    `X = XOR_ALL & XOR_ALL = XOR_ALL`
This remarkable simplification shows that the complex-looking xor-beauty is just the XOR sum of all elements in the array.

```java
class Solution {
    public int xorBeauty(int[] nums) {
        int xorSum = 0;
        for (int num : nums) {
            xorSum ^= num;
        }
        return xorSum;
    }
}
```
### Algorithm
*   Initialize a variable `result` to 0.
*   Iterate through each number `num` in the `nums` array.
*   Update the result by XORing it with the current number: `result ^= num`.
*   After the loop, return `result`.

# Solutions
### Java

```java
class Solution {
public
  int xorBeauty(int[] nums) {
    int ans = 0;
    for (int x : nums) {
      ans ^= x;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int xorBeauty(vector<int> &nums) {
    int ans = 0;
    for (auto &x : nums) {
      ans ^= x;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def xorBeauty(self, nums: List[int]) -> int: return reduce(xor, nums)

```