Find Xor-Beauty of Array solution and explanation
9 more videos on this problem
Find Xor-Beauty of Array || leetcode Biweekly 95 || Leetcode MediumBinaryMagic · 8:09 · 1K views
C. Find Xor - Beauty of Array - LEETCODE BIWEEKLY CONTEST 95 (Code + Explanation in details)Joyjit Codes · 3:03 · 1K views
Find Xor Beauty of Array | Leetcode 2527 | Leetcode BiWeekly contest 95Tech Courses · 9:43 · 901 views
2527. Find Xor-Beauty of Array (Leetcode Medium)Programming Live with Larry · 17:42 · 795 views
Biweekly Contest 95 | Find Xor-Beauty of Array (With PROOFs)codingMohan · 16:55 · 660 views
2527 Find Xor-Beauty of Array | LeetCode | C++ | Beginner Friendly ExplanationDeep Tech · 6:01 · 612 views
Find Xor Beauty of Array #leetcode #leetcodesolution #leetcodequestions #xor #contest #gfg #codingServer Side Truths · 2:52 · 378 views
【每日一题】LeetCode 2527. Find Xor-Beauty of ArrayHuifeng Guan · 22:14 · 370 views
Find Xor-Beauty of Array | Leetcode biweekly contestA Code Daily! · 5:13 · 339 views
2527. Find Xor-Beauty of Array | Biweekly Contest 95 | LeetCode | DCC NIT-ADCC NITA · 8:08 · 261 views
The 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 | 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
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.
def xorBeauty(nums):
xorBeauty = 0
n = len(nums)
for i in range(n):
for j in range(n):
for k in range(n):
xorBeauty ^= ((nums[i] | nums[j]) & nums[k])
return xorBeauty
if __name__ == "__main__":
nums = [1, 4]
print(xorBeauty(nums))import java.util.List;
public class XorBeauty {
public static int xorBeauty(List<Integer> nums) {
int xorBeauty = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
xorBeauty ^= ((nums.get(i) | nums.get(j)) & nums.get(k));
}
}
}
return xorBeauty;
}
public static void main(String[] args) {
List<Integer> nums = List.of(1, 4);
System.out.println(xorBeauty(nums));
}
}#include <iostream>
#include <vector>
int xorBeauty(std::vector<int>& nums) {
int xorBeauty = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
xorBeauty ^= ((nums[i] | nums[j]) & nums[k]);
}
}
}
return xorBeauty;
}
int main() {
std::vector<int> nums = {1, 4};
int result = xorBeauty(nums);
std::cout << result << std::endl;
return 0;
}function xorBeauty(nums) {
let xorBeauty = 0;
let n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
xorBeauty ^= ((nums[i] | nums[j]) & nums[k]);
}
}
}
return xorBeauty;
}
console.log(xorBeauty([1, 4]));#include <stdio.h>
int xorBeauty(int* nums, int numsSize) {
int xorBeauty = 0;
for (int i = 0; i < numsSize; ++i) {
for (int j = 0; j < numsSize; ++j) {
for (int k = 0; k < numsSize; ++k) {
xorBeauty ^= ((nums[i] | nums[j]) & nums[k]);
}
}
}
return xorBeauty;
}
int main() {
int nums[] = {1, 4};
int result = xorBeauty(nums, 2);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
class XorBeautySolution {
public static int XorBeauty(List<int> nums) {
int xorBeauty = 0;
int n = nums.Count;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
xorBeauty ^= ((nums[i] | nums[j]) & nums[k]);
}
}
}
return xorBeauty;
}
static void Main(string[] args) {
List<int> nums = new List<int> { 1, 4 };
Console.WriteLine(XorBeauty(nums));
}
}The Python solution performs a brute force calculation with three nested loops to evaluate every potential triplet of indices. Each triplet's effective value is XORed to find the xor-beauty value for the array.
Time Complexity: O(n^3) since three nested loops iterate over the list.
Space Complexity: O(1), requiring only a few auxiliary variables.
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.
def xorBeauty(nums):
xorBeauty = 0
for num in nums:
xorBeauty ^= num
return xorBeauty
if __name__ == "__main__":
nums = [1, 4]
print(xorBeauty(nums))import java.util.List;
public class XorBeauty {
public static int xorBeauty(List<Integer> nums) {
int xorBeauty = 0;
for (int num : nums) {
xorBeauty ^= num;
}
return xorBeauty;
}
public static void main(String[] args) {
List<Integer> nums = List.of(1, 4);
System.out.println(xorBeauty(nums));
}
}#include <iostream>
#include <vector>
int xorBeauty(std::vector<int>& nums) {
int xorBeauty = 0;
for (int num : nums) {
xorBeauty ^= num;
}
return xorBeauty;
}
int main() {
std::vector<int> nums = {1, 4};
int result = xorBeauty(nums);
std::cout << result << std::endl;
return 0;
}function xorBeauty(nums) {
let xorBeauty = 0;
for (let num of nums) {
xorBeauty ^= num;
}
return xorBeauty;
}
console.log(xorBeauty([1, 4]));#include <stdio.h>
int xorBeauty(int* nums, int numsSize) {
int xorBeauty = 0;
for (int i = 0; i < numsSize; i++) {
xorBeauty ^= nums[i];
}
return xorBeauty;
}
int main() {
int nums[] = {1, 4};
int result = xorBeauty(nums, 2);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
class XorBeautySolution {
public static int XorBeauty(List<int> nums) {
int xorBeauty = 0;
foreach (int num in nums) {
xorBeauty ^= num;
}
return xorBeauty;
}
static void Main(string[] args) {
List<int> nums = new List<int> { 1, 4 };
Console.WriteLine(XorBeauty(nums));
}
}The Python code leverages the properties of XOR to compute the final result by XORing all array elements sequentially. This approach skips the exhaustive triple-loop process by relying on patterns observed in XOR operations.
Time Complexity: O(n), as it iterates through each element just once.
Space Complexity: O(1), requiring minimal variable space.
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.
function xorBeauty(nums: number[]): number {
return nums.reduce((acc, cur) => acc ^ cur, 0);
}func xorBeauty(nums []int) (ans int) {
for _, x := range nums {
ans ^= x
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force Calculation of XOR-Beauty | Time Complexity: O(n^3) since three nested loops iterate over the list. |
| Approach 2: Optimized Calculation Using XOR Properties | Time Complexity: O(n), as it iterates through each element just once. |
| Bit Manipulation | – |
Complexity analysis
| 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 |
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.