-2

I am asking this question in relation to the following problem : https://practice.geeksforgeeks.org/problems/count-pairs-with-given-sum5022/1

Given an array of N integers, and an integer K, find the number of pairs of elements in the array whose sum is equal to K.

Count pairs with given sum in O(n) time and O(n) space. Given n = 4, k = 6, arr = [1 5 7 1]

This is part of my code:

#define MOD 1000007
int getPairsCount(int arr[], int n, int k) {
    // long long int h[MOD] = {0}; // This is the one I used originally
    // but it given 3 as the answer for the input n = 4, k = 6, arr = [1 5 7 1],
    
    unordered_map<long long, long long> h; // But when using map, it gives correct output as 2

    long long int count = 0;
    
    for(int i=0;i<n;i++){
        h[arr[i]]+=1;
    }
    
    for(int i=0;i<n;i++){
        count+=h[k - arr[i]];
        
        if(k == 2*arr[i])count--;
    }
    
    return (count/2);
    }
};

Anyone please explain why there is a difference. MOD was chosen based on the max number arr[i] can have (arr[i]<=10^6). even using memset to set all values to 0 didn't work.

Then why there is a difference in using a map and array as hash?

Olivia Stork
  • 4,660
  • 5
  • 27
  • 40
DoomLord
  • 3
  • 6
  • 1
    What do you hope to learn from these contest/challenge/competitive coding/hacking sites? If it's to learn C++, you won't learn anything there. Like in this case, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program either runs slow, or fails to handle an obscure edge case. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Sam Varshavchik Jan 16 '21 at 17:01
  • @sam https://www.youtube.com/watch?v=IM-hdoevo5M&ab_channel=TheTEACHERSOCIOLOGY – πάντα ῥεῖ Jan 16 '21 at 17:04
  • Well, @πάνταῥεῖ -- a nifty analogy. Except that the airplanes did actually bring some stuff that was useful to the natives. – Sam Varshavchik Jan 16 '21 at 17:08
  • @Sam Yup, that's what got lost [there](https://en.wikipedia.org/wiki/Cargo_cult_programming). – πάντα ῥεῖ Jan 16 '21 at 17:10

1 Answers1

0

Basic debugging: verify that data is what you think it is. This is easier to do with a debugger, but streaming diagnostics also works. Let's look at the evaluation of count+=h[k - arr[i]] over several iterations (using the input from the question).

    for(int i=0;i<n;i++){
        std::cerr << "count += h[k - arr[i]]\t" // To remind us what we are looking at
                     "count += h[" << k << " - " << arr[i] << "]\t"
                     "count += h[" << k - arr[i] << "]\t"
                     << count << " += " << h[k - arr[i]] << "\n";
        count+=h[k - arr[i]];
        
        if(k == 2*arr[i])count--;
    }

Possible output (using the array instead of the unordered map):

count += h[k - arr[i]]  count += h[6 - 1]   count += h[5]   0 += 1
count += h[k - arr[i]]  count += h[6 - 5]   count += h[1]   1 += 2
count += h[k - arr[i]]  count += h[6 - 7]   count += h[-1]  3 += 140720947826640
count += h[k - arr[i]]  count += h[6 - 1]   count += h[5]   140720947826643 += 1

At this point, the problem should be obvious (at the very least, the iteration where the problem occurs should be obvious). Even though every long long value is a valid key for an unordered_map from long long to something, at least half of those values are invalid indices for an array.

JaMiT
  • 14,422
  • 4
  • 15
  • 31