Welcome to Subscribe On Youtube

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 1

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int uniqueXorTriplets(int[] nums) {
          int mx = 0;
          for (int x : nums) {
              mx = Math.max(mx, x);
          }
          mx <<= 1;
  
          boolean[] st = new boolean[mx];
          for (int a : nums) {
              for (int b : nums) {
                  st[a ^ b] = true;
              }
          }
  
          int[] s = new int[mx];
          for (int ab = 0; ab < mx; ab++) {
              if (st[ab]) {
                  for (int c : nums) {
                      s[ab ^ c] = 1;
                  }
              }
          }
  
          int ans = 0;
          for (int v : s) {
              ans += v;
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int uniqueXorTriplets(vector<int>& nums) {
          int mx = ranges::max(nums) << 1;
  
          vector<bool> st(mx, false);
          for (int a : nums) {
              for (int b : nums) {
                  st[a ^ b] = true;
              }
          }
  
          vector<int> s(mx, 0);
          for (int ab = 0; ab < mx; ab++) {
              if (st[ab]) {
                  for (int c : nums) {
                      s[ab ^ c] = 1;
                  }
              }
          }
  
          return accumulate(s.begin(), s.end(), 0);
      }
  };
  

• class Solution:
      def uniqueXorTriplets(self, nums: List[int]) -> int:
          mx = max(nums) << 1
          st = [False] * mx
          for a in nums:
              for b in nums:
                  st[a ^ b] = True
          s = [0] * mx
          for ab in range(mx):
              if st[ab]:
                  for c in nums:
                      s[ab ^ c] = 1
          return sum(s)
  
  

• func uniqueXorTriplets(nums []int) int {
  	mx := slices.Max(nums) << 1
  
  	st := make([]bool, mx)
  	for _, a := range nums {
  		for _, b := range nums {
  			st[a^b] = true
  		}
  	}
  
  	s := make([]int, mx)
  	for ab := 0; ab < mx; ab++ {
  		if st[ab] {
  			for _, c := range nums {
  				s[ab^c] = 1
  			}
  		}
  	}
  
  	ans := 0
  	for _, v := range s {
  		ans += v
  	}
  	return ans
  }
  
  

• function uniqueXorTriplets(nums: number[]): number {
      const mx = Math.max(...nums) << 1;
  
      const st = new Array<boolean>(mx).fill(false);
      for (const a of nums) {
          for (const b of nums) {
              st[a ^ b] = true;
          }
      }
  
      const s = new Array<number>(mx).fill(0);
      for (let ab = 0; ab < mx; ab++) {
          if (st[ab]) {
              for (const c of nums) {
                  s[ab ^ c] = 1;
              }
          }
      }
  
      let ans = 0;
      for (const v of s) {
          ans += v;
      }
      return ans;
  }
  
  

All Problems

All Solutions