Count the Triplets

Sandeep kamila
Last Updated: May 13, 2022

Introduction to the problem statement

We are given an array arr[] containing n integers. Our task is to find the number of triples (i, j, k), where i, j, k are the indices and (1 <= i < j < k <= n), such that at least one of the numbers can be written as the sum of the other two in the set (A i, A j, A k).

Examples: 

Input : arr[] = {2, 1, 4, 5, 3}

Output : 4

Explanation: The valid triplets are: (2, 1, 3), (1, 4, 3), (1, 4, 5), (2, 5, 3).

 

Input : arr[] = {1, 1, 3, 3, 1, 2, 2}

Output : 18

The above problem statement means we have to find three elements from the given array so that the sum of two elements is equal to the third element.

Approach

To solve the above problem, we will first perform two basic steps:

  1. Find the maximum value from the given array.
  2. Create a frequency table, which stores the frequency of every element in the given array.

 

Finding maximum value:

Here, we use the in-built max function for finding the maximum value from the given array. We store it in the maxm variable.

 

for(int i = 0 ; i < n; i++)   // n is the size of the array
{
   maxm = max( arr[i],  maxm );
}

 

Creating frequency table:

 

Int freq[maxm+1]={0};   // initially frequencies of all elements is 0

for(int i = 0 ; i < n ; i++) // n refers number of array elements
{
   freq[arr[i]]++;
}

 

For example:

arr[] : { 2, 3, 1, 3, 4, 5 }

Frequency table stores:

01  2345
01  1211

 

After the above steps, we initialise a variable ans=0 which stores the number of triplets satisfying the required conditions.

Now, there are four cases, and according to this, the number of ways is stored in ans variable.

Case 1: ( 0, 0, 0)

Suppose all the three numbers are (0, 0, 0). In that case, it can satisfy the triplet condition as 0+0=0, so we have to add all the combinations containing the frequency of 0 to our ans variable, which mathematically equals f(0)C3, here f(x) represents the frequency of the element x in our array and Cq represents the number of ways of choosing q numbers from p numbers.

f(0)C3 = [f(0)!] / [(f(0)-3)! — 3!] =  (freq[0] )* (freq[0]-1 )* (freq[0]-2) / 6

Now, add this to our ans variable:

ans = ans + (freq[0] )* (freq[0]-1 )* (freq[0]-2) / 6

Case 2: (0, x, x)

If the three numbers are (0, x,x), it satisfies the triplet condition as 0 + x = x.

Now, we need to count the total number of combinations that contain one 0 and two x, which mathematically equal f(x)C2 * f(0)C1. For calculating this, we use a loop for each value of x.

 

for(int i = 1;i< = maxm; i++)
{
   ans = ans + freq[0]*freq[i]*(freq[i]-1)/2;
}

 

Case 3: (x , x , 2x)

If the three numbers are (x, x, 2x), it satisfies the triplet condition as x+x = 2x.

Now, we need to count the total number of combinations that contain one 2x and two x, which mathematically equal f(x)C2 * f(2x)C1. For calculating this, we use a loop for each value of x.

 

for(int i = 1; 2*i <= maxm; i++) // 2 times i should also lie within maximum value
{
   ans = ans + freq[i]*(freq[i]-1)/2*freq[2*i];
}

 

Case 4: (x, y, x+y)

If the three numbers are (x, y, x+y), it satisfies the triplet condition as x + y = (x+y).

Now, we need to count the total number of combinations that contain one x, one y and onex+y, which mathematically equal f(x)C1 * f(y)C1*f(x+y)C1. For calculating this, we use a loop for each value of x and y.

 

for(int i = 1; i <= maxm; i++)
{
   for(int j = i+1;j+i <= maxm; j++)
   {
      ans = ans + freq[i]*freq[j]*freq[i+j];
   }
}

 

After considering all the cases, we finally return ans.

Code in C++

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

int CountTriplets(vector<int> v)
{
    int maxm = 0;

    for (int i = 0; i < v.size(); i++)
        maxm = max(maxm, v[i]);

    int freq[maxm + 1] = {0};

    for (int i = 0; i < v.size(); i++)
        freq[v[i]]++;

    int ans = 0; // counts the number of triplets

    // Case 1: (0, 0, 0)
    ans = ans + freq[0] * (freq[0] - 1) * (freq[0] - 2) / 6;

    // Case 2: (0, x, x)
    for (int i = 1; i <= maxm; i++)
        ans = ans + freq[0] * freq[i] * (freq[i] - 1) / 2;

    // Case 3: (x, x, 2*x)
    for (int i = 1; 2 * i <= maxm; i++)
        ans = ans + freq[i] * (freq[i] - 1) / 2 * freq[2 * i];

    // Case 4: (x, y, x + y)
    for (int i = 1; i <= maxm; i++) {
        for (int j = i + 1; i + j <= maxm; j++)
            ans = ans + freq[i] * freq[j] * freq[i + j];
    }

    return ans;
}

int main()
{
    vector<int> v = {1, 1, 3, 3, 1, 2, 2};
    cout << (CountTriplets(v));
    return 0;
}

 

Output

18

Complexity Analysis

Time Complexity: It is O(max(n, maxm 2)) as we are running two nested loops of size maxm and a single loop of size n.

Space complexity: It is O(1) as we require constant extra space.

Frequently asked questions

Q1.What is C++ Hashmap?

Ans: A hash table (also known as a hash map) is a data structure that maps keys to values. A hash table employs a hash function to generate an index into an array of buckets or slots from which the corresponding value can be retrieved.

 

Q2. What is meant by dynamic programming?

Ans: Dynamic Programming (DP) is an algorithmic technique for solving a problem by recursively breaking it down into simpler subproblems and taking advantage of the fact that the optimal solution to the overall problem depends on the optimal solution to its subproblems.

 

Q3. What is a string?

Ans: A string is a variable that stores a series of letters or other characters, such as "Namaste" or "Incredible India". To create a string, we do the same thing with different data types: we declare it first, then we can store a value in it.

Key Takeaways

So, this article discussed the approach of counting the triplets problem in which we see all the four cases and their solution with C++ code.

If you are a beginner, interested in coding and want to learn DSA, you can look for our guided path for DSA, which is free! 

In case of any comments or suggestions, feel free to post them in the comments section.

Was this article helpful ?
0 upvotes