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