Number Of Pairs With Given Sum

Moderate

0/80

Average time to solve is 39m

Contributed by

39 upvotes

Asked in companies

Problem statement

You have been given an integer array/list(arr) and a number 'Sum'. Find and return the total number of pairs in the array/list which when added, results equal to the 'Sum'.

Note:

Given array/list can contain duplicate elements.

(arr[i],arr[j]) and (arr[j],arr[i]) are considered same.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line contains 2 space-separated integers N and Sum.

The next line contains N space-separated integers representing array elements.

Output format :

Print the total number of pairs present in the array/list.

Constraints :

1 <= N <= 10^5
-10^4 <= Sum <= 10^4
-10^4 <=  arr[ i ] <= 10^4

Time Limit: 1 sec

Sample Input 1:

9 12
1 3 6 2 5 4 3 2 4

Sample Output 1:

Explanation For Sample Input 1:

Since there doesn't exist any pair with a sum equal to 12, so we print 0.

Sample Input 2:

6 10
2 8 10 5 -2 5

Sample Output 2:

Hint 1

Hint 2

Hint 3

Try to find the sum of every pair possible and match it with the ‘Sum’.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force Approach

Initialize the ans = 0
Run two loops first from i = 0 to n-1 and second from j = i+1 to n-1 and if arr[i] + arr[j] == Sum then increase the ans by 1.
Return ans

Time Complexity

O(N^2), where N is the size of the array.

As we are running two nested loops of size N.

Space Complexity

O(1)

As constant extra space is used.

(100% EXP penalty)

Number Of Pairs With Given Sum

Console