Count Triplets That Can Form Two Arrays of Equal XOR

Count Triplets That Can Form Two Arrays of Equal XOR - Problem

Array Hash Table Math Bit Manipulation Prefix Sum Medium

Given an array of integers arr, we want to select three indices i, j, and k where 0 <= i < j <= k < arr.length.

Let's define a and b as follows:

a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (i, j, k) where a == b.

Input & Output

Example 1 — Basic Case

$ Input: arr = [2,3,1,6,7]

› Output: 4

💡 Note: Four valid triplets: (0,1,1), (0,2,2), (2,3,4), (2,4,4). Each creates equal left and right XOR values.

Example 2 — Simple Array

$ Input: arr = [1,1,1,1]

› Output: 6

💡 Note: Multiple ways to split: any subarray of even length has XOR=0, creating many valid triplets.

Example 3 — Single Element Subarrays

$ Input: arr = [2,3,1,6]

› Output: 1

💡 Note: Only (2,3,3) works where left=[2,3] has XOR=1 and right=[1] has XOR=1.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array of integers to analyze

Find Splits

Look for ways to split into equal XOR parts

Count Valid

Return total count of valid triplets

Key Takeaway

🎯 Key Insight: Use XOR properties - if left XOR equals right XOR, then total range XOR equals 0

Asked in

a Amazon 15 M Microsoft 12 Apple 8 G Google 6

The key insight is recognizing that if two XOR subarrays are equal, their combined XOR equals 0. The optimal approach uses prefix XOR arrays and mathematical properties to reduce complexity from O(n³) to O(n²). Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Triple Nested Loop	O(n³)	O(1)	Try all possible (i,j,k) triplets and calculate XOR for each subarray
Mathematical Insight	O(n²)	O(n)	Use the key insight that if a == b, then the entire range XOR equals 0
Prefix XOR Optimization	O(n³)	O(n)	Use prefix XOR array to calculate range XOR in constant time

Triple Nested Loop — Algorithm Steps

Iterate through all possible i values
For each i, iterate through all valid j values
For each (i,j), iterate through all valid k values
Calculate XOR of left and right subarrays
Increment count if left XOR equals right XOR

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Triplets

Try all valid (i,j,k) combinations

Calculate XORs

Compute left and right subarray XORs

Compare

Count when left XOR equals right XOR

Code -

solution.c — C

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

int solution(int* arr, int n) {
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j; k < n; k++) {
                // Calculate XOR of left part (i to j-1)
                int leftXor = 0;
                for (int x = i; x < j; x++) {
                    leftXor ^= arr[x];
                }
                
                // Calculate XOR of right part (j to k)
                int rightXor = 0;
                for (int y = j; y <= k; y++) {
                    rightXor ^= arr[y];
                }
                
                if (leftXor == rightXor) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops with inner XOR calculations

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

89.2K Views

Medium Frequency

~15 min Avg. Time

1.8K 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

Triple Nested Loop — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler