Count triplets from a given range having sum of two numbers of a triplet equal to the third number
Given two integers L and R, the task is to find the number of unique triplets whose values lie in the range [L, R], such that the sum of any two numbers is equal to the third number.
Examples:
Input: L = 1, R = 3
Output: 3
Explanation: Three such triplets satisfying the necessary conditions are (1, 1, 2), (1, 2, 3) and (2, 1, 3).Input: L = 2, R = 6
Output: 6
Naive Approach: The simplest approach to solve the problem is to generate all possible triplets over the range [L, R] and count those triplets having sum of any two numbers from the pair equal to the third number. After checking for all the triplets, print the total count obtained.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number int totalCombination( int L, int R) { // to count the triplets. int count=0; for ( int i=L;i<=R;i++){ // for traversing for L to R and finding the triplets. for ( int j=L;j<=R;j++){ for ( int k=L;k<=R;k++){ if (i+j==k){ count++;} } } } return count; // rreturn the number of found triplets } // Driver Code int main() { int L = 1, R = 3; cout << totalCombination(L, R); return 0; } // This code is contributed by Naveen Kumar. |
Java
import java.util.*; public class Main { // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number public static int totalCombination( int L, int R) { // to count the triplets. int count = 0 ; for ( int i = L; i <= R; i++) { // for traversing for L to R and finding the triplets. for ( int j = L; j <= R; j++) { for ( int k = L; k <= R; k++) { if (i + j == k) { count++; } } } } return count; // rreturn the number of found triplets } // Driver Code public static void main(String[] args) { int L = 1 , R = 3 ; System.out.println(totalCombination(L, R)); } } //This code is contributed by Naveen Gujjar from Haryana |
Python3
# Python program for the above approach # Function to find the number of triplets # from the range [L, R] having sum of two # numbers from the triplet equal to the third number def total_combination(L, R): # to count the triplets. count = 0 for i in range (L, R + 1 ): # for traversing for L to R and finding the triplets. for j in range (L, R + 1 ): for k in range (L, R + 1 ): if i + j = = k: count + = 1 return count # return the number of found triplets # Driver Code L = 1 R = 3 print (total_combination(L, R)) # The code is contributed by Arushi Goel. |
Javascript
// JavaScript program for the above approach // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number function totalCombination(L, R) { // to count the triplets. let count = 0; for (let i = L; i <= R; i++) { // for traversing for L to R and finding the triplets. for (let j = L; j <= R; j++) { for (let k = L; k <= R; k++) { if (i + j == k) { count++; } } } } return count; // return the number of found triplets } // Driver Code let L = 1, R = 3; console.log(totalCombination(L, R)); |
C#
using System; class GFG { // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number static int totalCombination( int L, int R) { // to count the triplets. int count = 0; for ( int i = L; i <= R; i++) { // for traversing for L to R and finding // the triplets. for ( int j = L; j <= R; j++) { for ( int k = L; k <= R; k++) { if (i + j == k) { count++; } } } } return count; // return the number of found triplets } // Driver Code static void Main() { int L = 1, R = 3; Console.WriteLine(totalCombination(L, R)); } } // This code is contributed by user_dtewbxkn77n |
Output
3
Time Complexity: O((R – L)3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
- If the difference between the given range is less than L, then there doesn’t exist any such triplet having the sum of two numbers equal to the third number.
- If the difference between the given range is at least L, then (R – L) lies in the range L and R, i.e. {L, (R – L), R}. It can be observed that the sum of L and any other number in the range [L, R – L] is at most R.
- Therefore, the total number of possible valid triplets, where the first element is L is given by (R – L – L + 1).
- Similarly, when the first element is (L + 1), then the number of triplets is (R – L – L), and so on.
From the above observations, the total number of triplets forms an AP with the terms (R – L – L + 1), (R – L – L), (R – L – L – 1), ……… consisting of (R – L – L + 1) number of terms. Therefore, the total number of triplets is given by:
where, N is (R – L – L + 1)
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number int totalCombination( int L, int R) { // Stores the total number of triplets int count = 0; // Find the difference of the range int K = R - L; // Case 1: If triplets can't // be formed, then return 0 if (K < L) return 0; // Otherwise int ans = K - L; // Update the total number of triplets count = ((ans + 1) * (ans + 2)) / 2; // Return the count return count; } // Driver Code int main() { int L = 2, R = 6; cout << totalCombination(L, R); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number static int totalCombination( int L, int R) { // Stores the total number of triplets int count = 0 ; // Find the difference of the range int K = R - L; // Case 1: If triplets can't // be formed, then return 0 if (K < L) return 0 ; // Otherwise int ans = K - L; // Update the total number of triplets count = ((ans + 1 ) * (ans + 2 )) / 2 ; // Return the count return count; } // Driven Code public static void main(String[] args) { int L = 2 , R = 6 ; System.out.print(totalCombination(L, R)); } } // This code is contributed by susmitakundugoaldanga. |
Python3
# Python3 program for the above approach # Function to find the number of triplets # from the range [L, R] having sum of two # numbers from the triplet equal to the third number def totalCombination(L, R): # Stores the total number of triplets count = 0 # Find the difference of the range K = R - L # Case 1: If triplets can't # be formed, then return 0 if (K < L): return 0 # Otherwise ans = K - L # Update the total number of triplets count = ((ans + 1 ) * (ans + 2 )) / / 2 # Return the count return count # Driver Code if __name__ = = '__main__' : L, R = 2 , 6 print (totalCombination(L, R)) # This code is contributed by mohit kumar 29. |
C#
// C# program to implement // the above approach using System; class GFG { // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number static int totalCombination( int L, int R) { // Stores the total number of triplets int count = 0; // Find the difference of the range int K = R - L; // Case 1: If triplets can't // be formed, then return 0 if (K < L) return 0; // Otherwise int ans = K - L; // Update the total number of triplets count = ((ans + 1) * (ans + 2)) / 2; // Return the count return count; } // Driver Code public static void Main() { int L = 2, R = 6; Console.WriteLine(totalCombination(L, R)); } } // This code is contributed by sauravghosh0416. |
Javascript
<script> // Javascript program for the above approach // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number function totalCombination(L, R) { // Stores the total number of triplets let count = 0; // Find the difference of the range let K = R - L; // Case 1: If triplets can't // be formed, then return 0 if (K < L) return 0; // Otherwise let ans = K - L; // Update the total number of triplets count = ((ans + 1) * (ans + 2)) / 2; // Return the count return count; } let L = 2, R = 6; document.write(totalCombination(L, R)); </script> |
Output:
6
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us