3514. Number of Unique XOR Triplets II

Description

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).

 

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

 

Solutions

Solution: Math

• Time complexity: O(n²+mn)
• Space complexity: O(m)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const uniqueXorTriplets = function (nums) {
  const n = nums.length;
  const maxNum = Math.max(...nums);
  const maxK = 32 - Math.clz32(maxNum);
  const maxXor = 1 << maxK;
  const pairXor = Array.from({ length: maxXor }, () => false);
  const tripletXor = Array.from({ length: maxXor }, () => false);

  for (let a = 0; a < n; a++) {
    for (let b = a; b < n; b++) {
      const xor = nums[a] ^ nums[b];

      pairXor[xor] = true;
    }
  }

  for (let xor = 0; xor < maxXor; xor++) {
    if (!pairXor[xor]) continue;

    for (const num of nums) {
      tripletXor[xor ^ num] = true;
    }
  }

  return tripletXor.reduce((result, isVisited) => result + Number(isVisited), 0);
};