Number of Unique XOR Triplets II

Problem

You are given an integer array nums.

A XOR triplet is defined as the XOR of three elements nums[i] XOR nums[j] XOR nums[k] where i <= j <= k.

Return the number of unique XOR triplet values from all possible triplets (i, j, k).

Examples

Example 1

Input: nums = [1,3]
Output: 2
Explanation:
The possible XOR triplet values are:
* `(0, 0, 0) -> 1 XOR 1 XOR 1 = 1`
* `(0, 0, 1) -> 1 XOR 1 XOR 3 = 3`
* `(0, 1, 1) -> 1 XOR 3 XOR 3 = 1`
* `(1, 1, 1) -> 3 XOR 3 XOR 3 = 3`
The unique XOR values are `{1, 3}`. Thus, the output is 2.

Example 2

Input: nums = [6,7,8,9]
Output: 4
Explanation:
The possible XOR triplet values are `{6, 7, 8, 9}`. Thus, the output is 4.

Constraints

• 1 <= nums.length <= 1500
• 1 <= nums[i] <= 1500

Solution

Method 1 – Brute Force with Set

Intuition

We need to find all unique values of nums[i] ^ nums[j] ^ nums[k] for i ≤ j ≤ k. Since n ≤ 1500, a triple loop is feasible, and we can use a set to collect unique results.

Approach

1. Iterate over all i, j, k with i ≤ j ≤ k.
2. For each triplet, compute the XOR and add it to a set.
3. Return the size of the set.

Code

C++

class Solution {
public:
    int countTriplets(vector<int>& nums) {
        unordered_set<int> s;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                int x = nums[i];
                for (int k = j; k < n; ++k) {
                    x ^= (k == j ? 0 : nums[k]);
                    s.insert(x);
                }
            }
        }
        return s.size();
    }
};

Go

func countTriplets(nums []int) int {
    s := map[int]struct{}{}
    n := len(nums)
    for i := 0; i < n; i++ {
        for j := i; j < n; j++ {
            x := nums[i]
            for k := j; k < n; k++ {
                if k > j { x ^= nums[k] }
                s[x] = struct{}{}
            }
        }
    }
    return len(s)
}

Java

class Solution {
    public int countTriplets(int[] nums) {
        Set<Integer> s = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int x = nums[i];
                for (int k = j; k < n; k++) {
                    if (k > j) x ^= nums[k];
                    s.add(x);
                }
            }
        }
        return s.size();
    }
}

Kotlin

class Solution {
    fun countTriplets(nums: IntArray): Int {
        val s = mutableSetOf<Int>()
        val n = nums.size
        for (i in 0 until n) {
            for (j in i until n) {
                var x = nums[i]
                for (k in j until n) {
                    if (k > j) x = x xor nums[k]
                    s.add(x)
                }
            }
        }
        return s.size
    }
}

Python

class Solution:
    def countTriplets(self, nums: list[int]) -> int:
        s = set()
        n = len(nums)
        for i in range(n):
            for j in range(i, n):
                x = nums[i]
                for k in range(j, n):
                    if k > j:
                        x ^= nums[k]
                    s.add(x)
        return len(s)

Rust

use std::collections::HashSet;
impl Solution {
    pub fn count_triplets(nums: Vec<i32>) -> i32 {
        let mut s = HashSet::new();
        let n = nums.len();
        for i in 0..n {
            for j in i..n {
                let mut x = nums[i];
                for k in j..n {
                    if k > j { x ^= nums[k]; }
                    s.insert(x);
                }
            }
        }
        s.len() as i32
    }
}

TypeScript

class Solution {
    countTriplets(nums: number[]): number {
        const s = new Set<number>()
        const n = nums.length
        for (let i = 0; i < n; i++) {
            for (let j = i; j < n; j++) {
                let x = nums[i]
                for (let k = j; k < n; k++) {
                    if (k > j) x ^= nums[k]
                    s.add(x)
                }
            }
        }
        return s.size
    }
}

Complexity

• ⏰ Time complexity: O(n^3)
• 🧺 Space complexity: O(n^3) in the worst case (all triplets unique)