Aniket Vaishnav

Posted on

# Count the triplets

problem statement : https://practice.geeksforgeeks.org/problems/count-the-triplets4615/1#

Given an array of distinct integers. The task is to count all the triplets such that the sum of two elements equals the third element.

Example 1:

``````Input:
N = 4
arr[] = {1, 5, 3, 2}
Output: 2
Explanation: There are 2 triplets:
1 + 2 = 3 and 3 +2 = 5
``````

Example 2:

``````Input:
N = 3
arr[] = {2, 3, 4}
Output: 0
Explanation: No such triplet exits
``````

You don't need to read input or print anything. Your task is to complete the function countTriplet() which takes the array arr[] and N as inputs and returns the triplet count

Expected Time Complexity: O(N2)

Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 103
1 ≤ arr[i] ≤ 105

Solution Contains :

• Solution using HashMap [space complexity O(n)]
• Solution using 2 pointers [space complexity O(1)]

## Solution using HashMap

This solution is in java

``````import java.util.*;

class Solution {
int countTriplet(int a[], int n) {
// code here
int cnt = 0;
HashMap<Integer, Integer> map = new HashMap<>();
// value -> index

for(int i = 0; i < n; i++) {
// since it is distinct so no need to worry about duplicate values
map.put(a[i], i);
}

for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
Integer found = map.get(a[i] + a[j]);
if(found != null && found != i && found != j)
cnt ++;
}
}

return cnt;
}
}
``````

## Solution using two pointers

``````import java.util.*;
/**
* We will check for each number and say wether it could be decomposed into 2
* such that those 2 numbers after addition ends up being the source number.
*/

// complexity :
//      time  : O(n^2)
//      space : O(1)

public class TwoPointerSolution {
int countTriplet(int a[], int n) {
// code here
int cnt = 0;
Arrays.sort(a);
for(int i = 0; i < n; i++) {
cnt += decompose(a, a[i], 0, i-1);
}
return cnt;
}
int decompose(int[] a, int source, int from, int to) {
if(to >= a.length || from < 0 || from >= to) return 0;
int cnt = 0;
while(from < to) {
int testSum = a[from] + a[to];
if(testSum > source) {
to--;
} else if(testSum < source) {
from++;
} else {
cnt++; // inc. count
to--;    // shrink window
from++;  // as every elemet is distinct.
}
}
return cnt;
}
}
``````