Count triplets in an array such that i<j<k and a[j] – a[i] = a[k] – a[j] = D
Given an array arr and an integer D, the task is to count the number of triplets(arr[i], arr[j], arr[k]) in the array such that:
- i < j < k
- arr[j] – arr[i] = arr[k] – arr[j] = D
Examples:
Input: arr = {1, 6, 7, 7, 8, 10, 12, 13, 14}, D = 3
Output: 2
Explanation:
There are two triplets in the array that satisfies the given criteria.
-> 1st triplet(7, 10, 13) such that i = 3, j = 6 and k = 8, such that (i < j < k) and (10 – 7 = 13 – 10 = D (=3))
-> 2nd triplet(7, 10, 13) such that i = 4, j = 6 and k = 8, such that (i < j < k) and (10 – 7 = 13 – 10 = D (=3))Input: arr = {6, 3, 4, 5}, D = 1
Output: 0
Naive Approach: The simplest approach is using three nested for loops and find the triplets that satisfy the given criteria. Below is the implementation of this approach.
C++
// C++ program to count the triplets #include<bits/stdc++.h> using namespace std; // Function to count the triplets int CountTriplets( int arr[], int d, int n) { int count = 0; // Three nested for loops to count the // triplets that satisfy the given criteria for ( int i = 0; i < n - 2; i++) { for ( int j = i + 1; j < n - 1; j++) { for ( int k = j + 1; k < n; k++) { if ((arr[j] - arr[i] == d) && (arr[k] - arr[j] == d)) { count++; } } } } return count; } // Driver Code int main() { int A[] = { 1, 6, 7, 7, 8, 10, 12, 13, 14 }; int D = 3; int n = sizeof (A) / sizeof (A[0]); cout << (CountTriplets(A, D, n)); } // This code is contributed by chitranayal |
Java
// Java program to count the triplets class GFG { // Function to count the triplets static int CountTriplets( int [] arr, int d) { int count = 0 ; int n = arr.length; // Three nested for loops to count the // triplets that satisfy the given criteria for ( int i = 0 ; i < n - 2 ; i++) { for ( int j = i + 1 ; j < n - 1 ; j++) { for ( int k = j + 1 ; k < n; k++) { if ((arr[j] - arr[i] == d) && (arr[k] - arr[j] == d)) { count++; } } } } return count; } // Driver Code public static void main(String args[]) { int A[] = { 1 , 6 , 7 , 7 , 8 , 10 , 12 , 13 , 14 }; int D = 3 ; System.out.println(CountTriplets(A, D)); } } |
Python3
# Python3 program to count the triplets # Function to count the triplets def CountTriplets(arr, d): count = 0 ; n = len (arr); # Three nested for loops to count the # triplets that satisfy the given criteria for i in range (n - 1 ): for j in range (i + 1 , n - 1 ): for k in range (j + 1 , n): if ((arr[j] - arr[i] = = d) and (arr[k] - arr[j] = = d)): count + = 1 ; return count; # Driver Code if __name__ = = '__main__' : A = [ 1 , 6 , 7 , 7 , 8 , 10 , 12 , 13 , 14 ]; D = 3 ; print (CountTriplets(A, D)); # This code is contributed by Rajput-Ji |
C#
// C# program to count the triplets using System; class GFG { // Function to count the triplets static int CountTriplets( int [] arr, int d) { int count = 0; int n = arr.Length; // Three nested for loops to count the // triplets that satisfy the given criteria for ( int i = 0; i < n - 2; i++) { for ( int j = i + 1; j < n - 1; j++) { for ( int k = j + 1; k < n; k++) { if ((arr[j] - arr[i] == d) && (arr[k] - arr[j] == d)) { count++; } } } } return count; } // Driver Code public static void Main(String []args) { int []A = { 1, 6, 7, 7, 8, 10, 12, 13, 14 }; int D = 3; Console.WriteLine(CountTriplets(A, D)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to count the triplets // Function to count the triplets function CountTriplets(arr, d) { let count = 0; let n = arr.length; // Three nested for loops to count the // triplets that satisfy the given criteria for (let i = 0; i < n - 2; i++) { for (let j = i + 1; j < n - 1; j++) { for (let k = j + 1; k < n; k++) { if ((arr[j] - arr[i] == d) && (arr[k] - arr[j] == d)) { count++; } } } } return count; } // Driver code let A = [ 1, 6, 7, 7, 8, 10, 12, 13, 14 ]; let D = 3; document.write(CountTriplets(A, D)); </script> |
2
Time Complexity: O(N3).
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Efficient Approach:
- An efficient approach for this problem is to use a map to store (key, values) pair where value will be count of key.
- The idea is to traverse the array from 0 to N and do following:
- check that A[i] – D and A[i] – 2*D are present in the map or not.
- If it’s in the map then we will simply multiply their respective values and increase answer by that.
- Now, we just have to put A[i] into the map and update the map.
Below is the implementation of the above approach.
C++14
// C++14 program to count the number // of triplets from an array. #include<bits/stdc++.h> using namespace std; // Function to count the triplets int countTriplets ( int arr[], int d, int n) { int count = -1; // Create a map to store (key, values) pair. map< int , int > set; // Traverse the array and check that we // have already put (a[i]-d and a[i]-2*d) // into map or not. If yes we have to get // the values of both the keys and // multiply them, else put a[i] into the map. for ( int i = 0; i < n; i++) { if ((set.find(arr[i] - d) != set.end()) && (set.find(arr[i] - 2 * d) != set.end())) { count += (set[arr[i] - d] * set[arr[i] - 2 * d]); } // Update the map if (set.find(arr[i]) == set.end()) set[arr[i]] = 1; else set[arr[i]] += 1; } return count; } // Driver Code int main() { // Test Case 1: int a1[] = { 1, 6, 7, 7, 8, 10, 12, 13, 14 }; int d1 = 3; cout << countTriplets(a1, d1, 9) << endl; // Test Case 2: int a2[] = { 6, 3, 4, 5 }; int d2 = 1; cout << countTriplets(a2, d2, 4) << endl; // Test Case 3: int a3[] = { 1, 2, 4, 5, 7, 8, 10 }; int d3 = 3; cout << countTriplets(a3, d3, 7) << endl; return 0; } // This code is contributed by himanshu77 |
Java
// Java program to count the number // of triplets from an array. import java.util.*; class GFG { // Function to count the triplets static int countTriplets( int [] arr, int d) { int count = - 1 ; // Create a map to store (key, values) pair. Map<Integer, Integer> set = new HashMap<>(); // Traverse the array and check that we // have already put (a[i]-d and a[i]-2*d) // into map or not. If yes we have to get // the values of both the keys and // multiply them, else put a[i] into the map. for ( int i = 0 ; i < arr.length; i++) { if (set.get(arr[i] - d) != null && set.get(arr[i] - 2 * d) != null ) { count += (set.get(arr[i] - d) * set.get(arr[i] - 2 * d)); } // Update the map. if (set.get(arr[i]) == null ) { set.put(arr[i], 1 ); } else { set.put(arr[i], set.get(arr[i]) + 1 ); } } return count; } // Driver Code public static void main(String args[]) { // Test Case 1: int a1[] = { 1 , 6 , 7 , 7 , 8 , 10 , 12 , 13 , 14 }; int d1 = 3 ; System.out.println(countTriplets(a1, d1)); // Test Case 2: int a2[] = { 6 , 3 , 4 , 5 }; int d2 = 1 ; System.out.println(countTriplets(a2, d2)); // Test Case 3: int a3[] = { 1 , 2 , 4 , 5 , 7 , 8 , 10 }; int d3 = 3 ; System.out.println(countTriplets(a3, d3)); } } |
Python3
# Python3 program to count the number # of triplets from an array. # Function to count the triplets def countTriplets (arr, d, n): count = - 1 # Create a map to store (key, values) pair. set = {} # Traverse the array and check that we # have already put (a[i]-d and a[i]-2*d) # into map or not. If yes we have to get # the values of both the keys and # multiply them, else put a[i] into the map. for i in range ( 0 , n): if ((arr[i] - d) in set .keys() and (arr[i] - 2 * d) in set .keys()): count + = ( set [arr[i] - d] * set [arr[i] - 2 * d]) # Update the map if (arr[i]) in set .keys(): set [arr[i]] + = 1 else : set [arr[i]] = 1 print (count) # Driver Code # Test Case 1: a1 = [ 1 , 6 , 7 , 7 , 8 , 10 , 12 , 13 , 14 ] d1 = 3 countTriplets(a1, d1, 9 ) # Test Case 2: a2 = [ 6 , 3 , 4 , 5 ] d2 = 1 countTriplets(a2, d2, 4 ) # Test Case 3: a3 = [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] d3 = 3 countTriplets(a3, d3, 7 ) # This code is contributed by Stream_Cipher |
C#
// C# program to count the number // of triplets from an array. using System; using System.Collections.Generic; class GFG { // Function to count the triplets static int countTriplets( int [] arr, int d) { int count = -1; // Create a map to store (key, values) pair. Dictionary< int , int > set = new Dictionary< int , int >(); // Traverse the array and check that we // have already put (a[i]-d and a[i]-2*d) // into map or not. If yes we have to get // the values of both the keys and // multiply them, else put a[i] into the map. for ( int i = 0; i < arr.Length; i++) { if ( set .ContainsKey(arr[i] - d) && set .ContainsKey(arr[i] - 2 * d)) { count += ( set [arr[i] - d] * set [arr[i] - 2 * d]); } // Update the map. if (! set .ContainsKey(arr[i])) { set .Add(arr[i], 1); } else { set [arr[i]] = set [arr[i]] + 1; } } return count; } // Driver Code public static void Main(String []args) { // Test Case 1: int []a1 = { 1, 6, 7, 7, 8, 10, 12, 13, 14 }; int d1 = 3; Console.WriteLine(countTriplets(a1, d1)); // Test Case 2: int []a2 = { 6, 3, 4, 5 }; int d2 = 1; Console.WriteLine(countTriplets(a2, d2)); // Test Case 3: int []a3 = { 1, 2, 4, 5, 7, 8, 10 }; int d3 = 3; Console.WriteLine(countTriplets(a3, d3)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to count the number // of triplets from an array. // Function to count the triplets function countTriplets(arr,d) { let count = -1; // Create a map to store (key, values) pair. let set = new Map(); // Traverse the array and check that we // have already put (a[i]-d and a[i]-2*d) // into map or not. If yes we have to get // the values of both the keys and // multiply them, else put a[i] into the map. for (let i = 0; i < arr.length; i++) { if (set.get(arr[i] - d) != null && set.get(arr[i] - 2 * d) != null ) { count += (set.get(arr[i] - d) * set.get(arr[i] - 2 * d)); } // Update the map. if (set.get(arr[i]) == null ) { set.set(arr[i], 1); } else { set.set(arr[i], set.get(arr[i]) + 1); } } return count; } // Driver Code // Test Case 1: let a1=[1, 6, 7, 7, 8, 10, 12, 13, 14]; let d1 = 3; document.write(countTriplets(a1, d1)+ "<br>" ); // Test Case 2: let a2=[6, 3, 4, 5 ]; let d2 = 1; document.write(countTriplets(a2, d2)+ "<br>" ); // Test Case 3: let a3=[1, 2, 4, 5, 7, 8, 10]; let d3 = 3; document.write(countTriplets(a3, d3)+ "<br>" ); // This code is contributed by avanitrachhadiya2155 </script> |
1 0 2
Time Complexity: O(NlogN), where N is the size of the given array.
Auxiliary Space: O(N),
Contact Us