Description
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 | val2is bitwise OR ofval1andval2.val1 & val2is bitwise AND ofval1andval2.
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 <= 1051 <= nums[i] <= 109
Solutions
Solution 1: Bit Manipulation
We first consider the case where i and j are not equal. In this case, ((nums[i] | nums[j]) & nums[k]) and ((nums[j] | nums[i]) & nums[k]) produce the same result, and their XOR result is 0.
Therefore, we only need to consider the case where i and j are equal. In this case, ((nums[i] | nums[j]) & nums[k]) = (nums[i] & nums[k]). If i ≠ k, then this is the same as the result of nums[k] & nums[i], and the XOR result of these values is 0.
Therefore, we ultimately only need to consider the case where i = j = k, and the answer is the XOR result of all nums[i].
The time complexity is O(n) and the space complexity is O(1), where n is the length of the array.
class Solution: def xorBeauty(self, nums: List[int]) -> int: return reduce(xor, nums)(code-box)
