3820. Number Of Unique Xor Triplets Ii¶
3820. Number of Unique XOR Triplets II
Medium
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 <= 15001 <= nums[i] <= 1500
Solution¶
class Solution {
public int uniqueXorTriplets(int[] nums) {
int n = nums.length;
int ele[] = new int[4000];
int set[] = new int[4000];
for (int x : nums) ele[x]++;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) set[nums[i] ^ nums[j]]++;
}
int count = 0;
for (int i = 0; i <= 2048; i++) {
for (int j = 0; j <= 2048; j++) {
if (set[j] > 0) {
int req = j ^ i;
if (req >= 4000) continue;
if (ele[req] > 0) {
count++;
break;
}
}
}
}
return count;
}
}
Complexity Analysis¶
- Time Complexity: O(?)
- Space Complexity: O(?)
Explanation¶
[Add detailed explanation here]