PROBLEM SETTER -
ZCO 2013
DIFFICULTY –
Easy
PREREQUISITES–
Sorting, 2-pointer
PROBLEM IN SHORT–
Given an array A of N integers and an integer K, find the number of pairs of indices (i,j) and (i \neq j), such that A[i] + A[j] is less than K.
FIRST SUBTASK SOLUTION –
It can be solved with a simple brute by trying all the C(N,2) pairs with a nested for loop by iterating over all pairs and adding 1 to the answer if sum of selected elements is less than K. Here is the implement for it –
for(int i = 1;i < n+1;i++) for(int j = i+1;j < n+1;j++) if(A[i] + A[j] < K) ans++; cout << ans;
TIME COMPLEXITY -
O(N^2)
KEY OBSERVATIONS -
1.Sorting the array would not change the answer, hence we sort it in ascending order.
2.Suppose, for an element A[i], we have an element A[j], such that A[i] + A[j] < K and A[i] + A[j+1] >= K.
Then, any integer with index less than j can pair with ith element to form a countable pair.
SECOND SUBTASK SOLUTION –
We will first sort the array in ascending order. Then, we will maintain 2 pointers – i and j, where i represents the current index we are present on and counting the number of pairs for. j represents the first integer such that A[i] + A[j] < K and A[i] + A[j+1] >= K. Then j also represents the number of integers such that i^{th} element can be paired with, according to observation 2.
So, for each i, we add (j-i) to the answer. Note that we don’t add simply j to the answer so as to avoid over-counting, as the number of pairs consisting of previous (i-1) integers as one of the number has already been counted. Then, we add 1 to i, and decrease j while A[i] + A[j] >= K and j > i. We keep doing this while j > i and i < N+1.
sort(a+1,a+n+1);
long long int ans=0,j=n;
for(int i = 1;i < n+1;i++)
{
while(a[i] + a[j] >= k && j>0)
j--;
if(j > i)
ans += (j-i);
else
break;
}
cout << ans;
Remember to store the answer in long long format as, N can be at most 10^5 and C(N,2), which can be the maximum answer won’t fit in type int.
TIME COMPLEXITY –
O(2*N + N*log(N))