Count Triplets

Problem Statement

An array of integers with the length n is presented to us as Arr[]. The objective is to determine the quantity of triplets (Arr[i],Arr[j],Arr[k]) such that any two numbers added together equal the third number.

Example

a, b, and c are members of Arr[] with indexes i, j, and k, respectively, such that 0<=i<j<k<n . Three for loops will be used to do this. If $x!=y!=z$ and $arr[x]+arr[y]=arr[z]$, increase the count. Let's use examples to clarify.

Input

Output

Explanation

• Arr{} = [ 1, 2, 2, 3, 4 ] =(1, 2, 3) → 1 + 2 = 3
• Arr{} = [ 1, 2, 2, 3, 4 ] =(1, 2, 3) → 1 + 2 = 3
• Arr{} = [ 1, 2, 2, 3, 4 ] =(1, 3, 4) → 1 + 3 = 4
• Arr{} = [ 1, 2, 2, 3, 4 ] =(2, 2, 4) → 2 + 2 = 4

Input/Output

• Input An array is given as input and its size.
• Output Output is a single integer denoting the number of triplets in the array.

Constraints

• $3 <= \text{N} <= 100$
• $0 <= \text{arr[i]} <= 1000$

Approach1: Simple Approach

Algorithm

• We start with an integer array named Arr[] that has been filled with random numbers.
• The length of Arr is stored in variable N.
• Function count_Triplets(int arr[],int n) takes an array, its length returns the triplets in which one of the numbers can be written as sum of the other two
• Consider that the number of triplets' initial variable count is 0.
• For each element of the triplet, traverse the array using three for loops.
• Outermost loop is $0<=i<n-2$, innermost loop is $i<j<n-1$ , and innermost loop is j<k<n.
• To see if $arr[i]+arr[j]==arr[k], arr[i]+arr[k]==arr[j]$, or $arr[k]+arr[j]==arr[i]$, check the equation. If true, increase the count.
• At the conclusion of all loops, count will contain the total number of triplets that satisfy the requirement.
• The result should be the count.

CPP Implementation:

Java Implementation

Python Implementation:

Output:

• Time Complexity: $O(N^3)$ where N is the size of the array. Since we are using three loops to iterate the array.
• Space Complexity: $O(1)$

Approach2: Efficient Approach (Using Hashing)

In this method, all combinations that result in any two integers added together equaling third integer , is calculated. If we pay close attention, we can see that there are only 4 scenarios that could meet the aforementioned requirement.

• (0, 0, 0): This triplet is legal since 0 + 0 = 0. Since we only need to take triplets into consideration among all potential frequencies of 0, the total number of ways is therefore equal to ${freq[0] \choose 3}$.
• (0, x, x): This triplet is valid since 0 + x = x. Since we only need to take into account the triplet having one 0 and two x among all possible frequencies of 0 and x, the total number of ways is therefore equal to ${freq[x] \choose 2}$ * ${freq[0] \choose 1}$.
• (x, x, 2x): This triplet is legal since x + x equals 2x. Because we only need to take into account the triplet containing one 2x and one x among all potential frequencies of x and 2x, the total number of ways is therefore equal to ${freq[x] \choose 2}$ * ${freq[2x] \choose 1}$.
• (x, y, x + y): The total number of ways is given by the formula ${freq[x] \choose 1}$ * ${freq[y] \choose 1}$ * ${freq[x+y] \choose 1}$, where we only need to take into account the triplet that contains all possible frequencies of x, y, and x + y.

where, freq[x] = number of times x is present, C-> Combination $(nCr= n!/((n-r)!*r!) )$

Algorithm

• Find the value of the array's maximum element, mx.
• Create a frequency array named freq with the size mx + 1 and store the frequencies of each element of the array A[].
• Create a count variable, then take each of the four following scenarios into account:
• Add ${freq[0] \choose 3}$ to count if the triplet is (0, 0, 0).
• Add ${freq[x] \choose 2}$ * ${freq[0] \choose 1}$ to count if the triplet is (0, x, x).
• Add ${freq[x] \choose 2}$ * ${freq[2x] \choose 1}$ to count if the triplet is (x, x, 2x).
• If the triplet is (x, y, x + y), multiply the count by ${freq[x] \choose 1}$ * ${freq[y] \choose 1}$ * ${freq[x+y] \choose 1}$.
• Return count.

C++ Implementation:

Java Implementation:

Python Implementation:

Output:

Time Complexity: $O(N^2)$ where N is the number of nodes of the binary tree. We are using two loops.

Space Complexity: $O(N)$, as a map is used. Since we are using frequency array to store values.