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.

If the numbers are limited to the value M, you could solve it using FFT in N+MlogM

Can you please explain little approach?

This problem is one of 3SUM variants, so there is no known

O(n^{2 - ε}) algorithm for it (for any ε > 0) unless numbers satisfy some additional constraints (for example, are small).okay if the numbers are less than a particular value suppose k<100 then how to approach ??

then u can solve with hashing .... it will not cause tle

Approach?

In that case you can make the frequency of any number <= 2 and solve it in O(k^2)