Find Xor-Beauty of Array

Med

#2307Time: 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.

Patterns

Math Bit Manipulation

Data structures

Array

Prompt

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:

The xor-beauty of the given array is 34.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach that directly implements the problem description. It iterates through all nnn 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.

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.

Walkthrough

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.

1class Solution {2    public int xorBeauty(int[] nums) {3        int n = nums.length;4        int xorBeauty = 0;5        for (int i = 0; i < n; i++) {6            for (int j = 0; j < n; j++) {7                for (int k = 0; k < n; k++) {8                    int effectiveValue = (nums[i] | nums[j]) & nums[k];9                    xorBeauty ^= effectiveValue;10                }11            }12        }13        return xorBeauty;14    }15}

Complexity

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.

Trade-offs

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).

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.

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.

Walkthrough

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.

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])
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]) ]
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.
Substituting Back: Replacing a_i with its definition, we get S_k = ⨁_{i} (nums[i] & nums[k]).
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]) ]
Swapping Summation Order: The order of XORing doesn't matter, so we can swap the summations: X = ⨁_{i} [ ⨁_{k} (nums[i] & nums[k]) ]
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])
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.

1class Solution {2    public int xorBeauty(int[] nums) {3        int xorSum = 0;4        for (int num : nums) {5            xorSum ^= num;6        }7        return xorSum;8    }9}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int xorBeauty(int[] nums) {4    int ans = 0;5    for (int x : nums) {6      ans ^= x;7    }8    return ans;9  }10}

1class Solution {2public:3  int xorBeauty(vector<int> &nums) {4    int ans = 0;5    for (auto &x : nums) {6      ans ^= x;7    }8    return ans;9  }10};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem