By Dhanadeepa_Red, history, 9 months ago, ,

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.

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.

•
• -12
•

 » 9 months ago, # |   +11 If the numbers are limited to the value M, you could solve it using FFT in N+MlogM
•  » » 9 months ago, # ^ |   0 Can you please explain little approach?
 » 9 months ago, # |   +8 This problem is one of 3SUM variants, so there is no known O(n2 - ε) algorithm for it (for any ε > 0) unless numbers satisfy some additional constraints (for example, are small).
•  » » 9 months ago, # ^ |   0 okay if the numbers are less than a particular value suppose k<100 then how to approach ??
•  » » » 9 months ago, # ^ |   0 then u can solve with hashing .... it will not cause tle
•  » » » » 9 months ago, # ^ |   0 Approach?
•  » » » 9 months ago, # ^ | ← Rev. 3 →   0 In that case you can make the frequency of any number <= 2 and solve it in O(k^2)