wish_me's blog

Count number of distinct pairs whose sum exists in the given array("In less then n2")
By wish_me, history, 7 years ago, In English

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.

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    okay if the numbers are less than a particular value suppose k<100 then how to approach ??

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

      → Reply