Find Xor-Beauty of Array - Practice Coding Problems

Find Xor-Beauty of Array - 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 | val2 is bitwise OR of val1 and val2.
val1 & val2 is bitwise AND of val1 and val2.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,4]

› Output: 1

💡 Note: All possible triplets: (0,0,0)→1, (0,0,1)→0, (0,1,0)→1, (0,1,1)→4, (1,0,0)→1, (1,0,1)→4, (1,1,0)→0, (1,1,1)→4. XOR result: 1⊕0⊕1⊕4⊕1⊕4⊕0⊕4 = 1

Example 2 — Single Element

$ Input: nums = [15]

› Output: 15

💡 Note: Only one triplet possible: (0,0,0) gives (15|15)&15 = 15&15 = 15

Example 3 — Three Elements

$ Input: nums = [1,2,3]

› Output: 2

💡 Note: Calculate all 27 possible triplets and XOR their effective values together

Constraints

1 ≤ nums.length ≤ 300
1 ≤ nums[i] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array nums = [1,4]

Calculate Triplets

Find ((nums[i]|nums[j]) & nums[k]) for all i,j,k

XOR Results

XOR all effective values to get final answer

Key Takeaway

🎯 Key Insight: XOR properties cause paired terms to cancel, dramatically reducing computation complexity

Asked in

G Google 15 M Microsoft 12

The key insight is recognizing that XOR operations cause most effective values to cancel out in pairs, leaving only specific diagonal terms. The optimal approach uses mathematical properties to reduce O(n³) brute force to O(n). However, the mathematical derivation is complex and the actual pattern requires careful analysis of all triplet combinations.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Optimization	O(n)	O(1)	Use XOR properties to recognize that most terms cancel out, only diagonal survives
Brute Force - Triple Nested Loop	O(n³)	O(1)	Calculate effective value for every possible triplet (i,j,k) and XOR them all

Mathematical Optimization — Algorithm Steps

Recognize XOR property: a ⊕ a = 0
Analyze all triplets and identify which ones appear in pairs
Discover that only triplets where i=j=k don't have a canceling pair
Simplify to just XOR of all array elements

Visualization

Tap to expand

Step-by-Step Walkthrough

All Triplets

Start with all n³ possible triplets

Cancellation

Most terms appear in pairs and cancel via XOR

Survivors

Only diagonal terms (i=j=k) remain

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        result ^= nums[i];
    }
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to XOR all elements

✓ Linear Growth

Space Complexity

O(1)

Only using one variable to accumulate result

✓ Linear Space

12.0K Views

Medium Frequency

~25 min Avg. Time

580 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler