Find Xor-Beauty of 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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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:

1
2
3
4
5


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

Solution

Method 1 – Mathematical Reduction (XOR of All Elements)

Intuition

Although the problem asks for the XOR of all possible triplets’ effective values, mathematical analysis shows that the XOR-beauty is simply the XOR of all elements in the array. This is because each element appears an odd number of times in the triplet combinations, and all other terms cancel out due to XOR properties.

Approach

Initialize a variable to store the result.
Iterate through the array and XOR each element with the result.
Return the final result.

Code

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8


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

1
2
3
4
5
6
7


func xorBeauty(nums []int) int {
    ans := 0
    for _, num := range nums {
        ans ^= num
    }
    return ans
}

1
2
3
4
5
6


class Solution:
    def xorBeauty(self, nums: list[int]) -> int:
        ans = 0
        for num in nums:
            ans ^= num
        return ans

1
2
3
4
5


impl Solution {
    pub fn xor_beauty(nums: Vec<i32>) -> i32 {
        nums.iter().fold(0, |acc, &x| acc ^ x)
    }
}

1
2
3
4
5
6
7
8
9


class Solution {
    xorBeauty(nums: number[]): number {
        let ans = 0;
        for (const num of nums) {
            ans ^= num;
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n), where n is the length of the array, since each element is processed once.
🧺 Space complexity: O(1), only a few variables are used.

Problem#

Examples#

Solution#

Method 1 – Mathematical Reduction (XOR of All Elements)#

Intuition#

Approach#

Code#

Complexity#