ZCO13003 - Editorial

editorial
, ,
1

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))

1 Like