Count the triplets

Published at

7/6/2021

Categories

4 categories in total

Author

7 person written this

obrutus

open

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

Your Task:

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(N²)

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;
    }
}

dev-resources.site

Count the triplets

Solution using HashMap

Solution using two pointers