Pair Sum
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

Question

Pair Sum

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

Accepted Answer

Brute Force

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’.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space for finding our resultant answer. Thus the space complexity will be O(1).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), Where ‘N’ represents the number of elements in the array/list ‘ARR’.

Since we are using two nested loops for finding a pair, thus the time complexity will be O(N ^ 2).

C++ (g++ 5.4)

/*
    Time complexity: O(N ^ 2)
    Space complexity: O(1) 

    Where 'N' represents the number of elements in the array/list 'ARR'.
*/

int pairSum(vector &arr, int n, int target) {
    // Variable to store the number of required pairs.
    int countPair = 0;

    // Iterate through each element of the array/list.
    for (int i = 0; i < n - 1; i++) {
        // For each outer element check if any element makes a pair with it.
        for (int j = i + 1; j < n; j++) {
            // If sum of a pair results in target, then increment the value of required pairs.
            if (arr[i] + arr[j] == target) {
                countPair++;
                break;
            }
        }
    }
    // If no pairs are found, then return -1.
    if (countPair == 0) {
        return -1;
    } 
    // Return the number of required pairs.
    return countPair;
}

Python (3.5)

"""
    Time complexity: O(N ^ 2)
    Space complexity: O(1) 

    Where 'N' represents the number of elements in the array/list 'ARR'.
"""

def pairSum(arr, n, target): 
    # Variable to store the number of required pairs.
    countPair = 0

    # Iterate through each element of the array/list.
    for i in range(n-1): 
        # For each outer element check if any element makes a pair with it.
        for j in range(i+1,n): 
            # If sum of a pair results in target, then increment the value of required pairs.
            if (arr[i] + arr[j] == target):
                countPair += 1
                break
            
    # If no pairs are found, then return -1.
    if (countPair == 0): 
        return -1
     
    # Return the number of required pairs.
    return countPair

Java (SE 1.8)

/*
	Time complexity: O(N ^ 2)
	Space complexity: O(1) 

	Where 'N' represents the number of elements in the array/list 'ARR'.
*/

public class Solution {
	public static int pairSum(int[] arr, int n, int target) {
		// Variable to store the number of required pairs.
		int countPair = 0;

		// Iterate through each element of the array/list.
		for (int i = 0; i < n - 1; i++) {
			// For each outer element check if any element makes a pair with it.
			for (int j = i + 1; j < n; j++) {
				// If sum of a pair results in target, then increment the value of required pairs.
				if (arr[i] + arr[j] == target) {
					countPair++;
					break;
				}
			}
		}
		// If no pairs are found, then return -1.
		if (countPair == 0) {
			return -1;
		} 
		// Return the number of required pairs.
		return countPair;
	}
}

Accepted Answer

Two Pointer 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’.

Space Complexity: O(1)Explanation:

O(1).

Since we are not using any extra space for finding our resultant answer. Thus the space complexity will be O(1).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ represents the number of elements in the array/list ‘ARR’.

Since for finding the count of pairs whose sum is equal to 'TARGET', we are traversing the 'ARR' once. Thus the time complexity will be O(N).

Python (3.5)

"""
    Time complexity: O(N)
    Space complexity: O(1) 

    Where 'N' represents the number of elements in the array/list 'ARR'.
"""

def pairSum(arr, n, target): 
    # Variable to store the number of required pairs.
    countPair = 0

    start = 0
    end = n - 1

    # Start comparing the elements from both the ends.
    while (start < end): 
        # If sum of a pair results in target, then increment the value of required pairs.
        if (arr[start] + arr[end] == target):
            countPair += 1
            # Reduce both the ends from respective sides.
            start += 1
            end -= 1
        
        # If pair sum if smaller then increase the left border for larger elements.
        elif (arr[start] + arr[end] < target): 
            start += 1
         
        # If pair sum if larger then decrease the right border for smaller elements.
        else:
            end -= 1
        
    # If no pairs are found, then return -1.
    if (countPair == 0):
        return -1
     
    # Return the number of required pairs.
    return countPair

Java (SE 1.8)

/*
	Time complexity: O(N)
	Space complexity: O(1) 

	Where 'N' represents the number of elements in the array/list 'ARR'.
*/

public class Solution {
	public static int pairSum(int[] arr, int n, int target) {
		// Variable to store the number of required pairs.
		int countPair = 0;

		int start = 0;
		int end = n - 1;

		// Start comparing the elements from both the ends.
		while (start < end) {
			// If sum of a pair results in target, then increment the value of required pairs.
			if (arr[start] + arr[end] == target) {
				countPair++;
				// Reduce both the ends from respective sides.
				start++;
				end--;
			} 
			// If pair sum if smaller then increase the left border for larger elements.
			else if (arr[start] + arr[end] < target) {
				start++;
			}
			// If pair sum if larger then decrease the right border for smaller elements. 
			else {
				end--;
			}
		}
		// If no pairs are found, then return -1.
		if (countPair == 0) {
			return -1;
		}
		// Return the number of required pairs.
		return countPair;
	}
}

C++ (g++ 5.4)

/*
    Time complexity: O(N)
    Space complexity: O(1) 

    Where 'N' represents the number of elements in the array/list 'ARR'.
*/

int pairSum(vector &arr, int n, int target) {
    // Variable to store the number of required pairs.
    int countPair = 0;

    int start = 0;
    int end = n - 1;

    // Start comparing the elements from both the ends.
    while (start < end) {
        // If sum of a pair results in target, then increment the value of required pairs.
        if (arr[start] + arr[end] == target) {
            countPair++;
            // Reduce both the ends from respective sides.
            start++;
            end--;
        }
        // If pair sum if smaller then increase the left border for larger elements.
        else if (arr[start] + arr[end] < target) {
            start++;
        } 
        // If pair sum if larger then decrease the right border for smaller elements.
        else {
            end--;
        }
    }
    // If no pairs are found, then return -1.
    if (countPair == 0) {
        return -1;
    } 
    // Return the number of required pairs.
    return countPair;
}

Accepted Answer

function pairSum(sortedArray , target){

    let count = 0
    let leftPointer = 0
    let rightPointer = sortedArray.length - 1

    while(leftPointer < rightPointer){
        let sum = sortedArray[leftPointer] + sortedArray[rightPointer]

        if(sum === target){
            count++;
            leftPointer ++
            rightPointer --
            

            //Remove duplicates from left
            while(leftPointer < rightPointer && sortedArray[leftPointer] === sortedArray[leftPointer -1]){
                leftPointer++
            }

            //Remove duplicates from right
            while(leftPointer < rightPointer && sortedArray[rightPointer] === sortedArray[leftPointer +1]){
                rightPointer--
            }
        }
        else if(sum < target){
            leftPointer ++;
        }else if(sum > target){
            rightPointer --;
        }
    }

    return count > 0 ? count : -1
}

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:

Example:

Input Format:

Output Format :

Note:

Constraints:

Top Deloitte Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Deloitte Software Developer