Arrays: Find a triplet that sum to a given value

Problem Statement:

Given an unsorted array and a key, you need to find 3 elements in the array that is equal to the key.

Example:

arr = {2, 1, 10, 4, 5}, sum = 9;
Output: 4, 5

Solution

This problem can be solved with many different approach, in this article we shall learn about below approaches:

1. Using 3 loops/brute force approach

In brute force method, we take 3 nested for loops and check if there exist 3 numbers that is equal to the sum.

2. Optimized approach

In this approach, we find if the element is present in the set. If it is present, then we will print the result.
Else we will insert element into the set.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_set>

using namespace std;

void get_triplets_using_brute_force(int arr[], int n, int sum) 
{ 
    for (int i = 0; i < n - 2; i++) 
    { 
        for (int j = i + 1; j < n - 1; j++) 
        { 
            for (int k = j + 1; k < n; k++) 
            { 
                if (arr[i] + arr[j] + arr[k] == sum) 
                { 
                    cout <<"The triplets using bruteforce are = "<< arr[i] << " "
                         << arr[j] << " "
                         << arr[k] << endl; 
                } 
            } 
        } 
    } 
} 

void get_triplets_using_hashing(int arr[], int n, int sum) 
{ 
    for (int i = 0; i < n - 1; i++) 
    { 
        unordered_set<int> s; 
        for (int j = i + 1; j < n; j++) 
        { 
            int x = sum - (arr[i] + arr[j]); 
            if (s.find(x) != s.end()) 
                cout<<"The triplets using hashing are = "<< x << " "<< arr[i]<< " "<< arr[j]<<endl; 
            else
                s.insert(arr[j]); 
        } 
    } 
} 



int main() 
{ 
    int arr[] = { 0, -1, 2, -3, 1 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    get_triplets_using_brute_force(arr, n, -2); 
    get_triplets_using_hashing(arr, n, -2); 
    return 0; 
} 

Output:

The triplets using bruteforce are = 0 -3 1
The triplets using bruteforce are = -1 2 -3
The triplets using hashing are = -3 0 1
The triplets using hashing are = 2 -1 -3

 

 

 

Write a Comment

Leave a Comment

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