How to print the count of all distinct pairs that their sum equals k more faster than O(n^2) c++?

Question

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (v[i] + v[j] == k)
                cnt++;
        }
    }
    cout << cnt;

    return 0;
}

This code searches for all distinct pairs that their sum equals k then count how many distinct pairs are equal to k. Is there a way to do this task faster e.g. faster than O(n^2).

@kiner_shah Interesting idea but I don't know how you would perform this. May be, you could write an answer and show how. — Scheff's Cat, Jul 14 '18 at 08:07
@Scheff, sort the `vector` and search, for every `v[i]`, value equal to `k - v[i]` in the vector. Use flags for optimization! The solution will have complexity as `O(nlogn)` rather than `O(n^2)` — kiner_shah, Jul 14 '18 at 08:09
Do you specifically want to avoid two loops, or you do want to speed the routine up from O(n^2) to something faster? Hopefully it's the second case, because the first seems rather pointless. In the second case, you can put numbers into a hash table, so your algorithm will be O(n). — geza, Jul 14 '18 at 08:11
@kiner_shah Still two nested loops though the time complexity would be less. (There is the additional effort for the sorting before...) — Scheff's Cat, Jul 14 '18 at 08:11
Somehow, this sounds like a typical assignment for [Dynamic Programming](https://en.wikipedia.org/wiki/Dynamic_programming) though I don't know rather nothing about DP. — Scheff's Cat, Jul 14 '18 at 08:12
@user202729 if you use goto to loop back to where you started then goto is a loop — john, Jul 14 '18 at 08:13
@john, recursion is just using system stack! It just has similar effect as a loop does. — kiner_shah, Jul 14 '18 at 08:14
[Very related](https://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number). — user202729, Jul 14 '18 at 08:18
[Possible duplciate](https://stackoverflow.com/questions/33862394/count-pairs-from-an-array-whose-sum-is-equal-to-a-given-number) (i.e., "check out the answer there, it works") — user202729, Jul 14 '18 at 08:19

score 1 · Answer 1 · answered Jul 14 '18 at 08:19

1

Put the numbers into a hash table, with their occurrence count, it's an O(n) operation.

Then for each v[i] number, check the hash table for k-v[i], and sum the count, it's an O(n) operation as well.

The result will be the summed count divided by 2.

answered Jul 14 '18 at 08:19

geza

27,491
6
55
117

The algorithm looks similar to [this answer](https://stackoverflow.com/a/33862540/5267751). (except that this one has more explanation) – user202729 Jul 14 '18 at 08:21
@user202729: yes, it's almost the same. The difference is that in my answer, there are no duplicated entries in the hash table, but I use a counter. And that algorithm uses `uniquePairs`, which is not necessary. Aside from these, the algorithms are the same. – geza Jul 14 '18 at 08:24
Can you please justify this "it's an O(n) operation as well."? – kiner_shah Jul 14 '18 at 08:26
@kiner_shah: finding an element in a hash table is O(1). Therefore finding n elements is O(n). – geza Jul 14 '18 at 08:27
1

@kiner_shah O(1) on average. – user202729 Jul 14 '18 at 08:27
@geza, C++ `map` takes logarithmic time for `find()` operation. See [link](http://www.cplusplus.com/reference/map/map/find/) – kiner_shah Jul 14 '18 at 08:28
1

@kiner_shah: yes, but `map` is not a hash table. If you want to use a hash table, use `unordered_map` – geza Jul 14 '18 at 08:30
1

@kiner_shah So...? Where is `map` mentioned in the answer? – user202729 Jul 14 '18 at 08:30
@geza, `unordered_map` will surely work, yes! @user202729, right! – kiner_shah Jul 14 '18 at 08:31

How to print the count of all distinct pairs that their sum equals k more faster than O(n^2) c++?

1 Answers1