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 <= 1051 <= nums[i] <= 109Problem Overview: You are given an integer array nums. The XOR-beauty is defined as the XOR of the value ((nums[i] | nums[j]) & nums[k]) for every possible triplet (i, j, k). A direct evaluation involves examining all triplets, but the expression has strong bit manipulation properties that drastically simplify the result.
Approach 1: Brute Force Calculation of XOR-Beauty (O(n3) time, O(1) space)
The straightforward method iterates through every triplet of indices i, j, and k. For each combination, compute ((nums[i] | nums[j]) & nums[k]) and accumulate the XOR of the result. This requires three nested loops and performs the bitwise operations for each triplet. The logic is easy to verify and mirrors the problem definition exactly. However, with n elements the number of operations becomes n^3, which grows quickly and is impractical for larger inputs.
This approach is useful for understanding the expression and validating the mathematical pattern behind the optimized solution. You directly apply |, &, and XOR across all combinations without any preprocessing. Since only a few integer variables are used, the space complexity remains constant.
Approach 2: Optimized Calculation Using XOR Properties (O(n) time, O(1) space)
The key observation comes from analyzing the bit contribution of the expression ((a | b) & c). When XOR is applied across every triplet, each bit position behaves independently. After expanding the expression and counting how many times each bit contributes, most terms cancel out due to XOR parity rules. What remains is simply the XOR of all elements in the array.
This means the XOR-beauty can be computed by iterating through the array once and maintaining a running XOR: result ^= nums[i]. No triplet enumeration is required. The algorithm runs in linear time and constant space while still producing exactly the same result as the brute force definition.
This optimization relies on properties of XOR and AND operations often used in array and math based bit problems. The insight is recognizing that XOR cancels values appearing an even number of times, which collapses the complex triplet expression into a simple aggregate XOR.
Recommended for interviews: Interviewers expect the XOR property insight. Showing the brute force approach demonstrates that you understand the definition, but deriving the O(n) XOR-only solution shows strong reasoning about bitwise operations and algebraic simplification.
This approach involves iterating over all possible triplets (i, j, k) and calculating their effective value using the formula ((nums[i] | nums[j]) & nums[k]). Then, XOR all these effective values to obtain the xor-beauty of the array. Given the constraints, this approach is feasible only for smaller input sizes.
The provided C code iterates through all possible triplets of indices i, j, k and calculates the effective value ((nums[i] | nums[j]) & nums[k]). It then XORs all these effective values to find the xor-beauty of the array. For larger arrays, this will be computationally expensive due to the triple nested loops.
Time Complexity: O(n^3) because three nested loops run over the length of nums.
Space Complexity: O(1) as no additional data structures are used.
This approach takes advantage of the XOR operation's properties and finds a pattern to reduce computation. Instead of going through all triplets, this method calculates using combinations and benefits from canceling similar terms, thus improving efficiency.
This C code uses the idea that the final xor-beauty can be simplified to the XOR of all elements in the array. As the pattern of combination and cancellations leads to a simple XOR operation, this can be proven in certain cases.
Time Complexity: O(n) because each element is visited once.
Space Complexity: O(1), as it only uses a few new variables.
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 neq 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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force Calculation of XOR-Beauty | Time Complexity: O(n^3) because three nested loops run over the length of nums. |
| Approach 2: Optimized Calculation Using XOR Properties | Time Complexity: O(n) because each element is visited once. |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplet Evaluation | O(n^3) | O(1) | Understanding the definition or validating results for small inputs |
| XOR Property Optimization | O(n) | O(1) | General case and interview solution using bit manipulation insight |
Find Xor-Beauty of Array || leetcode Biweekly 95 || Leetcode Medium • BinaryMagic • 1,834 views views
Watch 9 more video solutions →Practice Find Xor-Beauty of Array with our built-in code editor and test cases.
Practice on FleetCode