JavaScript program to find the number of unique triplets whose XOR is zero
JavaScript program to find the number of unique triplets whose XOR is zero is a common programming problem that requires finding the number of unique triplets in a given array whose XOR is equal to zero.
The XOR operation is a bitwise operator that takes two bits and returns 1 if the bits are different, and 0 if they are the same.
In this problem, we need to find all possible combinations of three numbers in the array, where the XOR of the triplet is zero.
There are several ways to solve this problem, such as using brute force, hashing, or sorting techniques.
However, in this tutorial, we will focus on using a hashing technique in JavaScript to provide a step-by-step solution.
Additionally, we will examine the time and space complexity of the solution, and provide sample code for a clearer understanding. Without further ado, let's dive into the tutorial.
Problem Statement
We are required to find the number of unique triplets in a given array whose XOR is equal to zero.
In other words, we need to find all possible combinations of three numbers in the array, where the XOR of the triplet is zero. Let’s understand this with examples.
Sample Examples
Example 1 −
Explanation − In this example, there is only one unique triplet with XOR equal to zero.
That is [4, 7, 3].
Example 2 −
Explanation − In this example, there are two unique triplets with XOR equal to zero.
These are [1, 14, 15] and [5, 10, 15].
Alright, as we understand the problem statement, it’s time to shift focus on various approaches to solve this problem and then pick the best-suited one.
Brute Force − The brute force approach involves finding all possible triplets in the array and checking if their XOR is equal to zero. However, this approach is not feasible for large arrays as it has a time complexity of O(n^3).
Sorting − The sorting approach involves sorting the array and then finding the triplets whose XOR is zero using a two-pointer approach. This approach has a time complexity of O(n^2logn) due to sorting, but it can be optimized to O(n^2) using a hash table.
Hashing − The hashing approach involves using a hash table to store the frequency of elements in the array. We can then iterate through all possible pairs of elements and check if their XOR is present in the hash table. If it is present, we add the frequency of that XOR value to our answer. This approach has a time complexity of O(n^2) and a space complexity of O(n).
Overall, the hashing approach is the most efficient approach to solve this problem as it has a time complexity of O(n^2) and requires only O(n) space.
The hashing approach is ideal for large arrays where the brute force method is not practical. Additionally, the hashing technique does not necessitate sorting, making it quicker than the sorting approach for this particular problem.
As a result, we will utilize the hashing technique to solve this problem in our tutorial.
Let's now delve into the hashing algorithm to comprehend how to execute this problem.
here's a JavaScript program that calculates the number of unique triplets in an array whose XOR is zero.
function findTriplets(arr) {
let count = 0;
for (let i = 0; i < arr.length - 2; i++) {
for (let j = i + 1; j < arr.length - 1; j++) {
for (let k = j + 1; k < arr.length; k++) {
if ((arr[i] ^ arr[j] ^ arr[k]) === 0) {
count++;
}
}
}
}
return count;
}
const arr = [1, 2, 3, 4, 5, 6];
const result = findTriplets(arr);
console.log(`Number of unique triplets with XOR zero: ${result}`);
Hashing Algorithm
Define a function named countTriplets with two parameters, an array of integers and its size.
Create an empty array s.
Traverse the array and push all the elements into the array s.
Initialize a variable named count to 0.
Traverse the array and for each element at index i, traverse the array for all elements after i, from index j = i + 1 to n-1.
Calculate the XOR of a[i] and a[j] and store it in a variable xr.
Check if xr is present in the array s and if xr is not equal to a[i] and xr is not equal to a[j], then increase the count by 1.
Once both the loops are completed, divide the count by 3 and return the result.
In the driver code, define an array a and its size n.
Call the countTriplets function with an array a and its size n as arguments and store the result in a variable named result.
As we understood the algorithm now we have to implement this algorithm using JavaScript. So, let’s execute this algorithm using JavaScript with the help of an example.
Example: Implementation of the hashing approach using JavaScript
The program counts the number of unique triplets in an array whose XOR is equal to zero.
It does so by using a hashing technique, specifically by creating a set of the input array to quickly check for values that are present, and then iterating over all pairs of values and checking if their XOR is present in the set.
If it is, then the count is incremented. The final count is divided by 3 to obtain the number of unique triplets.
// JavaScript program to count the number of unique triplets whose XOR is 0 function to count the number of unique triplets whose XOR is 0 function countTriplets(arr) { const n = arr.length; // To store values that are present const set = new Set(arr); // stores the count of unique triplets let count = 0; // traverse for all i, j pairs such that j>i for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // xor of a[i] and a[j] const xr = arr[i] ^ arr[j]; // if xr of two numbers is present, then increase the count if (set.has(xr) && xr !== arr[i] && xr !== arr[j]) count++; } } // returns answer return Math.floor(count / 3); } // Driver code const arr = [1, 3, 5, 10, 14, 15]; console.log(countTriplets(arr));
Conclusion
To sum up, we have seen how to solve the problem of counting the number of unique triplets in an array whose XOR is zero.
We explored various approaches, including brute force, sorting, and hashing. Among these, the hashing technique provides the most efficient solution in terms of time complexity.
We have also implemented the hashing technique using JavaScript and validated it with examples.
It is important to note that this problem has many real-world applications, such as in cryptography and data compression.
By understanding this problem and its solutions, we can better appreciate the power and versatility of programming languages like JavaScript.
---------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------
MORE BLOG POSTS
Comments
Post a Comment