Find all triplets with zero-sum in C++ (Hash Tables)

In this C++ tutorial, we will learn to Find all triplets with zero-sum in C++. To solve this problem in this tutorial we are going to use hash tables.

Introduction

In this problem, we have to find triplets with sum equals to zero. This means if we have three elements x,y,z. And we add them we get zero as our result i.e x+y+z=0.

There are many ways to solve this problem.

One of them is to run three loops and find each element one by one. The problem with this method is that it has a time complexity of O(n3). This is a very high amount of time for a problem and if we increase the size of the array its time increases very high.

Another method for solving this problem is to use Hashing Table. Hashing is a method in which the value is saved with the index and can be retrieved very fast.

In this tutorial, we are going to solve the problem using hash tables.

Program to find all Triplets with zero-sum in C++

#include<bits/stdc++.h> 
using namespace std; 

void triplets(int arr[], int n) 
{ 
    bool found = false; 
  
    for (int i=0; i<n-1; i++) 
    {  
        unordered_set<int> s; 
        for (int j=i+1; j<n; j++) 
        { 
            int x = -(arr[i] + arr[j]); 
            if (s.find(x) != s.end()) 
            {
            	cout<<x<<arr[i]<<arr[j];
                found = true; 
            } 
            else
                s.insert(arr[j]); 
        }
    }
  
    if (found == false) 
        cout << " No Triplet Found" << endl; 
} 
  
int main() 
{
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++){
    cin>>arr[i];
  } 
    triplets(arr, n); 
    return 0; 
}

Input and Output

Enter the number of elements : 
4
Enter the elements
2
-2
0
1
-2 2 0

In the above code Firstly we enter the number of elements in the array. Secondly, function triplet is called with arguments one array and another one is the number of elements in the array. Further, the function runs and print the triplets.

The function triplet Firstly creates an unorderd_set which is also called a hash table. After that values are traversed to check if it is a triplet. On the other hand, if it does not satisfy that condition then the item is added to the table.

Finally, this method is faster than the three loops is takes O(n2) time. Which is much faster.

Conclusion

This method is Hash Tables (unordered_list) is very versatile. We can use hash tables in many different places in problems where we have to count or the number of items is required.

Also Checkout:

How to sort a Matrix in C++

Leave a Reply

Your email address will not be published. Required fields are marked *