Skip to main content
Talentd

Find Xor-Beauty of Array - Solution & Explanation

MediumArrayMathBit Manipulation15 min readAsked at: Amazon
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109

Approach Overview

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

Approach 1: Approach 1: Brute Force Calculation of XOR-Beauty

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Optimized Calculation Using XOR Properties

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) because each element is visited once.
Space Complexity: O(1), as it only uses a few new variables.

Try this approach in the editor →

Approach 3: 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 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force Calculation of XOR-Beauty

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.

Approach 2: Optimized Calculation Using XOR Properties

Time Complexity: O(n) because each element is visited once.
Space Complexity: O(1), as it only uses a few new variables.

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triplet EvaluationO(n^3)O(1)Understanding the definition or validating results for small inputs
XOR Property OptimizationO(n)O(1)General case and interview solution using bit manipulation insight

Video Solution

Find Xor-Beauty of Array || leetcode Biweekly 95 || Leetcode Medium • BinaryMagic • 1,890 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Xor-Beauty of Array easy or hard?
The implementation is easy once the key insight is known, but recognizing the XOR property makes it a medium-level problem. Many developers initially attempt the O(n^3) brute force approach before discovering the mathematical simplification.
Find Xor-Beauty of Array Python/Java solution
In Python or Java, iterate through the array and XOR every element into a result variable. Example logic: result ^= num for each number in nums. The same idea works in C++, JavaScript, C#, and other languages with identical O(n) time complexity.
How to solve Find Xor-Beauty of Array in O(n)?
Use the property that XOR cancels values appearing an even number of times. When expanding the triplet expression across all combinations, all intermediate terms cancel out except the individual numbers themselves. Iterating through the array and computing a running XOR of all elements produces the final XOR-beauty in O(n).
What is the best approach for Find Xor-Beauty of Array?
The optimal approach uses XOR properties to simplify the expression. Instead of evaluating every triplet, the XOR-beauty equals the XOR of all elements in the array. This reduces the complexity from O(n^3) to O(n) with constant space.
Is Find Xor-Beauty of Array asked at Google/Amazon/Meta?
Problems involving XOR simplification and bit manipulation patterns commonly appear in interviews at companies like Google, Amazon, and Meta. While this exact question may vary, understanding XOR cancellation and bitwise reasoning is frequently tested.
What data structure is used in Find Xor-Beauty of Array?
The solution primarily uses basic array traversal and bitwise operations. No advanced data structures are required; a single integer variable maintains the running XOR result.
What is the time complexity of Find Xor-Beauty of Array?
The brute force method that evaluates ((nums[i] | nums[j]) & nums[k]) for every triplet runs in O(n^3) time. The optimized solution computes the XOR of all array elements in a single pass, giving O(n) time and O(1) space.

Ready to solve this problem?

Practice Find Xor-Beauty of Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Decode XORed Permutation