Given an array arr[] of size N, consisting of distinct elements, the task is to count the number triplets such that (arr[j] – arr[i]) ? (arr[k] – arr[j]) ? 2 * (arr[j] – arr[i]) and arr[i] < arr[j] < arr[k] (1 ? i, j, k ? N and each of them should be distinct).
Examples:
Input: arr[] = {5, 3, 12, 9, 6}
Output: 4
Explanation: All triplets satisfying the conditions are {3, 5, 9}, {3, 6, 9}, {3, 6, 12}, {6, 9, 12}Input: arr[] = {1, 2, 3}
Output: 1
Naive Approach: The simplest approach is to generate all possible triplets and for each of them, check if it satisfies the given conditions or not.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by Binary Search. Follow the steps below to solve the problem:
- Sort the array arr[].
- Initialize a variable, say ans as 0, to store the number of triplets.
- Iterate over the range [1, N] using a variable i and perform the following steps:
- Iterate in the range [i+1, N] using the variable j and perform the following steps:
- Initialize X as arr[j] – arr[i].
- Find the lower bound of arr[j]+X using lower_bound and store its index in the variable l.
- Similarly, find the upper bound of arr[j] + 2×X using the default function upper_bound and store its index in the variable r.
- Add r-l to the variable ans.
- Iterate in the range [i+1, N] using the variable j and perform the following steps:
- After performing the above steps, print ans as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int countTriplets(int arr[], int N){ // Sort the array sort(arr, arr + N); // Stores count of triplets int l, r, i, j, ans = 0; // Iterate over the range [1, N] for (i = 0; i < N; i++) { // Iterate over the range [i+1, N] for (j = i + 1; j < N; j++) { // Required difference int x = arr[j] - arr[i]; // Find lower bound of arr[j] + x // and upper bound of arr[j] + 2*x l = lower_bound(arr, arr + N, arr[j] + x) - arr; r = upper_bound(arr, arr + N, arr[j] + 2 * x) - arr; // Adjust the indexing of arr[j]+2*r if (r == N || arr[r] != arr[j] + 2 * x) r -= 1; // From l to r, count number of // triplets by using arr[i] and arr[j] ans += r - l + 1; } } // return main ans return ans;}// Driver codeint main(){ int arr[] = { 1, 2, 3 }; int N = sizeof(arr) / sizeof(arr[0]); int ans = countTriplets(arr, N); cout << ans; return 0;} |
Java
// Java program for the above approachimport java.util.Arrays;class GFG{ public static int countTriplets(int arr[], int N){ // Sort the array Arrays.sort(arr); // Stores count of triplets int l, r, i, j, ans = 0; // Iterate over the range [1, N] for(i = 0; i < N; i++) { // Iterate over the range [i+1, N] for(j = i + 1; j < N; j++) { // Required difference int x = arr[j] - arr[i]; // Find lower bound of arr[j] + x // and upper bound of arr[j] + 2*x l = lower_bound(arr, 0, arr.length - 1, arr[j] + x); r = upper_bound(arr, 0, arr.length - 1, arr[j] + 2 * x); // Adjust the indexing of arr[j]+2*r if (r == N || arr[r] != arr[j] + 2 * x) r -= 1; // From l to r, count number of // triplets by using arr[i] and arr[j] ans += r - l + 1; } } // Return main ans return ans;}public static int upper_bound(int[] arr, int low, int high, int X) { // Base Case if (low > high) return low; // Find the middle index int mid = low + (high - low) / 2; // If arr[mid] is less than // or equal to X search in // right subarray if (arr[mid] <= X) { return upper_bound(arr, mid + 1, high, X); } // If arr[mid] is greater than X // then search in left subarray return upper_bound(arr, low, mid - 1, X);}public static int lower_bound(int[] arr, int low, int high, int X){ // Base Case if (low > high) { return low; } // Find the middle index int mid = low + (high - low) / 2; // If arr[mid] is greater than // or equal to X then search // in left subarray if (arr[mid] >= X) { return lower_bound(arr, low, mid - 1, X); } // If arr[mid] is less than X // then search in right subarray return lower_bound(arr, mid + 1, high, X);}// Driver codepublic static void main(String args[]){ int arr[] = { 1, 2, 3 }; int N = arr.length; int ans = countTriplets(arr, N); System.out.println(ans);}}// This code is contributed by gfgking |
Python3
# Python3 program for the above approach# Import library to apply# binary search and find boundfrom bisect import bisect_left# Function to count triplets# from an array that satisfies# the given conditionsdef countTriplets(arr, N): # Sort the array arr.sort() # Stores count of triplets ans = 0 # Iterate over the range [1, N] for i in range(N): # Iterate over the range [i+1, N] for j in range(i+1, N): # Required difference x = arr[j]-arr[i] # Find lower bound of arr[j] + x # and upper bound of arr[j] + 2*x l = bisect_left(arr, arr[j] + x) r = bisect_left(arr, arr[j] + 2*x) # Adjust the indexing of arr[j]+2*r if r == N or arr[r] != arr[j]+2*x: r -= 1 # From l to r, count number of # triplets by using arr[i] and arr[j] ans += r-l+1 # return main ans return ans# Driver Codeif __name__ == "__main__": # Given Input arr = [1, 2, 3] N = len(arr) # Function Call ans = countTriplets(arr, N) print(ans) |
C#
// C# program for the above approachusing System;class GFG { static int countTriplets(int[] arr, int N) { // Sort the array Array.Sort(arr); // Stores count of triplets int l, r, i, j, ans = 0; // Iterate over the range [1, N] for(i = 0; i < N; i++) { // Iterate over the range [i+1, N] for(j = i + 1; j < N; j++) { // Required difference int x = arr[j] - arr[i]; // Find lower bound of arr[j] + x // and upper bound of arr[j] + 2*x l = lower_bound(arr, 0, arr.Length - 1, arr[j] + x); r = upper_bound(arr, 0, arr.Length - 1, arr[j] + 2 * x); // Adjust the indexing of arr[j]+2*r if (r == N || arr[r] != arr[j] + 2 * x) r -= 1; // From l to r, count number of // triplets by using arr[i] and arr[j] ans += r - l + 1; } } // Return main ans return ans; } static int upper_bound(int[] arr, int low, int high, int X) { // Base Case if (low > high) return low; // Find the middle index int mid = low + (high - low) / 2; // If arr[mid] is less than // or equal to X search in // right subarray if (arr[mid] <= X) { return upper_bound(arr, mid + 1, high, X); } // If arr[mid] is greater than X // then search in left subarray return upper_bound(arr, low, mid - 1, X); } static int lower_bound(int[] arr, int low, int high, int X) { // Base Case if (low > high) { return low; } // Find the middle index int mid = low + (high - low) / 2; // If arr[mid] is greater than // or equal to X then search // in left subarray if (arr[mid] >= X) { return lower_bound(arr, low, mid - 1, X); } // If arr[mid] is less than X // then search in right subarray return lower_bound(arr, mid + 1, high, X); } static void Main() { int[] arr = { 1, 2, 3 }; int N = arr.Length; int ans = countTriplets(arr, N); Console.WriteLine(ans); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script>// JavaScript program for the above approachfunction countTriplets(arr, N) { // Sort the array arr.sort((a, b) => a - b); // Stores count of triplets let l, r, i, j, ans = 0; // Iterate over the range [1, N] for (i = 0; i < N; i++) { // Iterate over the range [i+1, N] for (j = i + 1; j < N; j++) { // Required difference let x = arr[j] - arr[i]; // Find lower bound of arr[j] + x // and upper bound of arr[j] + 2*x l = lower_bound(arr, 0, arr.length - 1, arr[j] + x); //console.log(l) console.log(arr, arr[j] + 2 * x) r = upper_bound(arr, 0, arr.length - 1, arr[j] + 2 * x); console.log(r) // Adjust the indexing of arr[j]+2*r if (r == N || arr[r] != arr[j] + 2 * x) r -= 1; // From l to r, count number of // triplets by using arr[i] and arr[j] ans += r - l + 1; } } // return main ans return ans;}function upper_bound(arr, low, high, X) { // Base Case if (low > high) return low; // Find the middle index let mid = Math.floor(low + (high - low) / 2); // If arr[mid] is less than // or equal to X search in // right subarray if (arr[mid] <= X) { return upper_bound(arr, mid + 1, high, X); } // If arr[mid] is greater than X // then search in left subarray return upper_bound(arr, low, mid - 1, X);}function lower_bound(arr, low, high, X) { // Base Case if (low > high) { return low; } // Find the middle index let mid = Math.floor(low + (high - low) / 2); // If arr[mid] is greater than // or equal to X then search // in left subarray if (arr[mid] >= X) { return lower_bound(arr, low, mid - 1, X); } // If arr[mid] is less than X // then search in right subarray return lower_bound(arr, mid + 1, high, X);}// Driver codelet arr = [1, 2, 3];let N = arr.length;let ans = countTriplets(arr, N);document.write(ans);</script> |
Output
1
Time Complexity: O(N2*log(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
