Find Xor-Beauty of Array - Video Solutions

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(n³) 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.