Count the Triplets

Introduction

Hey, Ninjas! This blog will cover one of the interesting problems related to counting triplets. This is also one of the problems which are asked in most of the technical interviews.

Before we dive deep into the solution to this problem, we should look at a sample example to better understand this problem.

Problem Statement

We are given an array arr[] containing ‘n’ integers. We need to count the number of triplets (i, j, k) where ‘i’, ‘j’, and ‘k’ are indices. It should satisfy the conditions where we can write at least one number as the sum of the other two in the set {A _i, A _j, A _k} and1 <= i < j < k <= n.

Examples
 

Input 

arr[] = {2, 2, 4, 6, 10}

Output 

4
 

Explanation

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. 

From the set, we can get the following triplets:

• 2 + 2 = 4, i.e., (2, 2, 4)
• 2 + 4 = 6, i.e., (2, 4, 6)
• 2 + 4 = 6, i.e., (2, 4, 6)
• 4 + 6 = 10, i.e., (4, 6, 10)

Since , 2 is occurring twice above; hence, there are two separate sets of (2, 4, 6).

The valid triplets are: (2, 2, 4), (2, 4, 6), (2, 4, 6), (4, 6, 10).

Brute Force Approach

The most basic approach that comes to our mind is to run three nested loops from 1 to N and count the number of triplets in an array where the sum of two numbers in the triplet is equal to the third number.

Algorithm

1. A function “countTriplets” is initialized that takes an array “arr” and “n” which is the length of the array and counts the number of triplets such that one number is the sum of the other two.
2. Sort the array in ascending order.
3. Use three nested loops to count the number of triplets start, mid and end such that start < mid < end.
4. Check if the sum of A[start] + A[mid] is equal to A[end]. If yes, increment the count.
5. After all possible combinations are checked, return the count.

Dry Run

1. A function “countTriplets” is initialized that takes an array “arr” {2, 2, 4, 6, 10} and “n” which is the length of the array i.e., 6 and counts the number of triplets such that one number is the sum of the other two.
2. Sort the array “arr”.
3. The table will show each iteration and how the count is getting incremented.

 4. As it can be seen from the table, count is 4. Hence the function prints 4.

Code in C++

#include <iostream>
using namespace std;

int countTriplets(int arr[], int n){
    // Initialize count to 0.
    int cnt = 0;
    /* 
        Run three nested loops, If 
        arr[i] + arr[j] == arr[k] increment count 
    */
    for(int start = 0; start < n; start++){
        for(int mid = start + 1; mid < n; mid++){
            for(int end = mid + 1; end < n; end++){
                if(arr[start] + arr[mid] == arr[end]){
                    cnt++;
                }
            }
        }
    }
    // Finally return count
    return cnt;
}
int main(){
    int arr[] = {2, 2, 4, 6, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // Call the function and print the result 
    int count = countTriplets(arr, n);
    cout << "Number of Triplets are " << count << endl;

    return 0; 
}

Output

Complexity

Time Complexity
It is O(N³) because there are three nested loops that run to find the count of triplets.

Space complexity
It is O(1), as we are not using any kind of space throughout the code.

Optimized Approach

We need to count the number of triplets in an array where the sum of two numbers in the triplet is equal to the third number. We will first create a frequency vector to store the count of each element of the input array. We then count the number of triplets of different forms using the frequency vector and return the count. Finally, we call the ‘printTriplets’ function, which prints the number of triplets.

Algorithm

1. The function "getfrequency" is called that takes an array "arr" of integers and its size "n" as input.
    
2. Find the maximum element "maxi" in the input array.
    
3. Now, create a frequency vector "freq" which keeps track of the count of each element of the input array “arr” of size "maxi+1" and initializes all its elements to zero.
    
4. Return the frequency vector "freq".
    
5. Now we call a function "countTriplets" that takes the frequency vector "freq" and the maximum integer "maxi" as input.
    
6. Initialize a variable "count" to zero.
    
7. Count the number of triplets of the form (0,0,0) and add it to "count".

• Case 1: ( 0, 0, 0)
  Consider a case when all three numbers in the given array are 0. In this case, the triplet condition is satisfied as the sum of any two numbers equals 0. Therefore, we need to include all combinations that involve the frequency of 0 in the count. Mathematically, this can be expressed as “f(0)C₃”, where f(x) represents the frequency of element ‘x’ in the array and ^p C_q represents the number of ways of choosing ‘q’ numbers from ‘p’ numbers.
  f(0)C₃ = [f(0)!] / [(f(0)-3)! — 3!] =  (freq[0] )* (freq[0]-1 )*(freq[0]-2)/ 6
   

 8. Count the number of triplets of the form (0, i, i) and add it to "count" for each integer ‘i’ from 1 to "maxi".

• Case 2: (0, x, x)
  Now consider a scenario when the three numbers in a triplet are (0, x, x), and they meet the condition of 0 + x = x. To determine the total number of combinations that include one 0 and two x, the formula “f(x)C₂ * f(0)C₁” can be used.
   

 9. Count the number of triplets of the form (i, j, 2*i+j) and add it to "count" for each integer ‘i’ from 1 to "maxi/2".

• Case 3: (x , x , 2x)
  Now, 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)C₂ * f(2x)C₁.
   

 10. Count the number of triplets of the form (i, j, k) and add it to "count" for each pair of integers (i, j) such that i+j is less than or equal to "maxi".

• 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 one x+y, which mathematically equal f(x)C₁ * f(y)C₁*f(x+y)C₁.

 11. Return the "count" variable.

 12. Finally, print the triplets using the "printTriplets" function that takes an array "arr" of integers and its size "n" as input.

Dry Run

1. We need to find the number of triplets for the array arr[] = {2, 2, 4, 6, 10} such that one number is the sum of the other two and 1 <= i < j < k <= n.
    
2. The function “printTriplets” calls the function “getfrequency” with ‘arr’ and ‘n’ as input.
    
3. The function “getfrequency” calculates the maximum value of the input array, i.e., 10.
    
4. Now, initialize a frequency vector “freq” with 11 elements (0 to 10) and set all elements to 0.
    
5. Iterate each element of the input array and increment the corresponding element in the frequency vector. 
    
6. The frequency array looks like:

 7. Now, enter the “countTriplets” function where a count variable is initialized as 0.

 8. For the first condition, it says to count the triplets of the form (0, 0, 0). We can use the formula: 

• From the frequency table, it is clearly visible that freq[0] is 0. Hence, the count remains 0.

 9. For the second condition, we need to count the triplets of the form (0, i, i), we can use the formula. The ‘maxi’ value is 10.

• From the frequency table again, we see that freq[0] is 0. Hence, the count still remains 0.

 10. Now for the third condition, we need to count the triplets of the form (i, j, 2*i+j), here we can use the formula.

• From the table, we can see when ‘i’ corresponds to 2, the count is 1. Hence, the ‘count’ is updated to 1.

 11. Now for the final condition, we need to count the triplets of the form (i, j, k), here we can use the formula.

• From the frequency table, we can see that there is only freq[2], freq[4], freq[6], freq[10] for which frequencies are greater than 1.

• From the table,the value of count is 3 from the final condition. Therefore, the count is further updated to 1+3 = 4. 

 12. Finally, the “countTriplet” function returns 4, which is the required result.

Code in C++

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

/* 
    Function to get the frequency
    vector of the input vector 
*/
vector<int> getfrequency(int arr[], int n) {
    // Maximum element in the array
    int maxi = *max_element(arr, arr+n);
    
    // frequency vector 
    vector<int> freq(maxi + 1, 0);
    
    /*
        Count and store frequency of each 
        character from the input array 
    */
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
    }

    return freq;
}

// Function to count the number of triplets 
int countTriplets(vector<int>& freq, int maxi) {
    // Initilize count to 0.
    int count = 0;  

    // Count the number of triplets of the form (0,0,0)
    count += freq[0] * (freq[0] - 1) * (freq[0] - 2) / 6;

    // Count the number of triplets of the form (0, i, i)
    for (int i = 1; i <= maxi; i++) {
        count += freq[0] * freq[i] * (freq[i] - 1) / 2;
    }

    // Count the number of triplets of the form (i, j, 2*i + j)
    for (int i = 1; 2 * i <= maxi; i++) {
        count += freq[i] * (freq[i] - 1) / 2 * freq[2 * i];
    }
    
    // Count the number of triplets of the form (i, j, k)
    for (int i = 1; i <= maxi; i++) {
        for (int j = i + 1; i + j <= maxi; j++) {
            count += freq[i] * freq[j] * freq[i + j];
        }
    }

    return count;
}

// Function for printing the triplets
void printTriplets(int arr[], int n) {
    
    // Frequency vector for the input vector
    vector<int> freq = getfrequency(arr, n);
    int maxi = freq.size() - 1;
    
    // Count number of triplets and get the result
    int triplets = countTriplets(freq, maxi);
    cout << "Number of triplets are " << triplets << endl;
}
int main(){
    int arr[] = {2, 2, 4, 6, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // Call the function and print the result 
    printTriplets(arr, n);

    return 0; 
}

Output

Complexity

Time Complexity
It is O(N²) because the last loop iterates over all possible pairs of elements in the array.

Space complexity
It is O(maxi), maxi is the maximum element in the array. This is because the frequency vector has maxi+1 elements.

Frequently Asked Questions

What is C++ Hashmap?

A hash table is a form of 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.

What is a string?

A string is a group of characters stored as a variable. It is enclosed in double quotes.

What is the time complexity for the sort() STL function?

The time complexity of the sort() STL function is O(n log n) on average, where n represents the input length.

What is a frequency array?

An array that keeps the count of the occurrences of elements.

How can you find the length of an array in C++?

You can use the ‘size()’ method in C++ to find the length of an array.

Conclusion

In this blog, we learned the problem of counting the triplets. We have implemented the problem in C++ programming language.

For more similar articles, you can refer following links:
 

• Count triplets with sum smaller than a given value
• Kth Distinct String in an Array
• Kth lexicographically smallest distinct String from given Array of Strings
   

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Codestudio. Also, you can enrol in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!