Last Updated: 18 Feb, 2021

Pair Sum

Easy

Asked in companies

Solve now

Problem statement

You are given an array/list ‘ARR’ consisting of ‘N’ distinct integers arranged in ascending order. You are also given an integer ‘TARGET’. Your task is to count all the distinct pairs in ‘ARR’ such that their sum is equal to ‘TARGET’.

Note:

1. Pair (x,y) and Pair(y,x) are considered as the same pair. 

2. If there exists no such pair with sum equals to 'TARGET', then return -1.

Example:

Let ‘ARR’ = [1 2 3] and ‘TARGET’ = 4. Then, there exists only one pair in ‘ARR’ with a sum of 4 which is (1, 3). (1, 3) and (3, 1) are counted as only one pair.

Input Format:

The first line of input contains an integer ‘T’ which denotes the number of test cases. 

The first line of each test case contains two single space-separated integers ‘N’ and ‘TARGET’ representing the number of elements in the array/list ‘ARR’ and the required pair-sum respectively.

The next line of each test case contains ‘N’ single space-separated integers denoting the elements of  ‘ARR’.

Output Format :

For each test case, return the numbers of pairs in  ‘ARR’ whose sum is equal to ‘TARGET’.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= ‘T’ <= 100
2 <= ‘N’ <= 5000
1 <= ‘ARR[i]’, ‘TARGET’ <= 10^5

Where ARR[i]’ represents the elements of array/list ‘ARR’. 

Time Limit: 1 sec

Solve now

Approaches

01 Approach

First, we declare a variable 'COUNTPAIR’ in which we store all pairs whose sum is equal to 'TARGET’. Then, we traverse the array ‘ARR’ and assume every element as the first element of the pair. Then we again traverse the remaining array and consider every element as a second element of the pair, and check whether the sum of the two elements is equal to 'TARGET' or not. If it is equal to 'TARGET',’ then we increase our ‘COUNTPAIR’ by 1.

The steps are as follows:

We declare a variable ‘COUNTPAIR’ and initialize it with 0.
We run a loop for ‘i’ = 0 to ‘N’ - 1:
- We run a loop for ‘j’ = ‘i’ + 1 to ‘N’:
  - If ‘ARR[i]’ + ‘ARR[j]’ is equal to 'TARGET':
    - ‘COUNTPAIR’++
    - We break the loop as the elements are sorted and distinct. So, the pair sum will increase and can't be equal to ‘TARGET’.
If ‘COUNTPAIR’ is equal to ‘0’:
- Then, Return - 1.
Else
- Return ‘COUNTPAIR’.

Solve now

02 Approach

We can optimize our solution. We know the array/list elements are present in sorted order, so we can apply two pointers technique. We declare two variables, 'START' and 'END', and initialize 'START' with 0 and 'END' with 'N' - 1.

Then we run a loop while the 'START' is less than the 'END'. In every iteration, we have three possibilities:

First, ‘ARR[start]’ + ’ARR['END']’ is equal to 'TARGET'. Then we increase our ‘COUNTPAIR’ by 1, and we increment 'START' by 1 and decrement 'END’ by 1.
Second, if ‘ARR['START']’ + ’ARR['END']’ is greater than 'TARGET'. That means the sum of our selected pair is greater than the ‘TARGET’, so we decrease 'END' by 1.
Third, if ‘ARR['START']’ + ’ARR['END']’ is less than 'TARGET'. That means the sum of our selected pair is less than the ‘TARGET’, so we increase the 'START' by 1.

The steps are as follows:

We declare a variable ‘COUNTPAIR’ in which we store a number of pairs whose sum is equal to 'TARGET'. We declare two variables ‘START’ and 'END' and initialize them as discussed above.
We run a loop while ‘START’ is less than 'END':
- If ‘ARR[‘START’]’ + ’ARR['END']’ is equal to 'TARGET':
  - ‘COUNTPAIR’++
  - ‘START’++
  - 'END'--
- If ‘ARR[‘START’]’ + ’ARR['END']’ is less than 'TARGET' :
  - ‘START’++
- Else
  - 'END'--
If ‘COUNTPAIR’ is equal to ‘0’ :
- Then, Return - 1.
Else
- Return ‘COUNTPAIR’.

Solve now