Practice
Contest Link
Problem Link
Author- Suprodip Kundu
Tester- Abhishek Paul,Sayan Poddar
Editorialist- Suprodip Kundu
DIFFICULTY:
EASY
PREREQUISITES:
Array, Two Pointers
PROBLEM:
In the problem you have to find the combinations, where the sum of any two numbers is greater than the third number.
EXPLANATION:
First we have to sort the array and then traverse the array from n-1 to 2(where n is the size of the array) and fix greater element.
Now use the Two Pointers algorithm to find if there is a pair whose sum is greater than the third number.
TIME COMPLEXITY:
O(N^2)
SPACE COMPLEXITY:
O(1)
SOLUTION:
"Setter's Solution" C++
#include<bits/stdc++.h>
#define Suprodip ios_base::sync_with_stdio(false);
#define Kundu cin.tie(NULL);cout.tie(NULL);
#define all(x) (x).begin(),(x).end()
#define ll long long
#define endl "\n"
#define mod 1e9+7
using namespace std;
long long combi(vector<int>& nums,int n)
{
sort(all(nums));
ll count=0;
for(int k=n-1;k>1;k--)
{
int i=0;
int j=k-1;
while(i<j)
{
if(nums[i]+nums[j]>nums[k])
{
count=count+(j-i);
j--;
}
else
i++;
}
}
return count;
}
int main()
{
//freopen("ip1.in", "r", stdin);
//freopen("op1.out", "w", stdout);
Suprodip Kundu
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++)
cin>>arr[i];
cout<<combi(arr,n)<<endl;
}
return 0;
}
"Tester's Solution" Java
import java.util.*;
class Sept1
{
static long combi(long nums[],int n)
{
Arrays.sort(nums);
int k=n-1;
long count=0;
for(;k>1;k--)
{
int i=0;
int j=k-1;
while(i<j)
{
if(nums[i]+nums[j]>nums[k])
{
count=count+(j-i);
j--;
}
else
i++;
}
}
return count;
}
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int t=Integer.parseInt(sc.nextLine());
while(t>0)
{
int n=Integer.parseInt(sc.nextLine());
String s[]=sc.nextLine().split(" ");
long a[]=new long[s.length];
for(int i=0;i<s.length;i++)
{
a[i]=Long.parseLong(s[i]);
}
long c=combi(a,a.length);
System.out.println(c);
t--;
}
}
}
"Tester's Solution" Python
for _ in range(int(input())):
n=int(input())
nums = list(map(int, input().split()))
count=0
nums.sort()
for i in range (2,len(nums)):
left=0
right=i-1
while(left<right):
if (nums[left]+nums[right]>nums[i]):
count=count+(right-left)
right=right-1
else:
left=left+1
print(count)