Блог пользователя Amit_Badshah

Автор Amit_Badshah, история, 3 месяца назад, По-английски,

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.

 
 
 
 
  • Проголосовать: нравится  
  • -12
  • Проголосовать: не нравится  

»
3 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +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).