Count number of distinct pairs whose sum exists in the given array("In less then n2")

Revision en1, by wish_me, 2017-09-14 10:29:48

Given an array of N positive integers. Count the number of pairs whose sum exists in the given array. While repeating pairs will not be counted again. And we can’t make a pair using same position element. Eg : (2, 1) and (1, 2) will be considered as only one pair.

I was able to solve problem in O(n2).I want a solution less then this.

Please read all examples carefully.

Examples:

Input : arr[] = {1, 2, 3, 5, 10}

Output : 2

Explanation : Here there are two such pairs:

(1 + 2) = 3, (2 + 3) = 5.

Note : Here we can't take pair (5, 5) as

we can see 5 is not coming twice

Input : arr[] = {1, 5, 6, 4, -1, 5}

Output : 4

Explanation : (1 + 5) = 6, (1 + 4) = 5,

(5 + -1) = 4, (6 + -1) = 5

Note : Here (1, 5) comes twice will be

considered as only one pair.

Input : arr[] = {5, 5, 5, 5, 10}

Output : 1

Explanation : (5 + 5) = 10

Note : Here (5, 5) comes twice will be

considered as only one pair.

Tags array

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English wish_me 2017-09-14 10:29:48 1047 Initial revision (published)