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#
Java#
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;
}
}
|
C++#
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
}
|
Python#
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
|
Rust#
1
2
3
4
5
|
impl Solution {
pub fn xor_beauty(nums: Vec<i32>) -> i32 {
nums.iter().fold(0, |acc, &x| acc ^ x)
}
}
|
TypeScript#
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.