0

I was solving leetcode problem (Pairs of Songs With Total Durations Divisible by 60) and my solution below uses a map, when I change it to an unordered_map and print the elements inside the loop; the number of elements are much more than the input

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        map<int, int> mod_d;
        
        for(auto el : time) {
            if(mod_d.count(el % 60) == 0) {
                mod_d[el % 60] = 1;
            }else mod_d[el % 60]++;
        }
        
        int ans = 0, i = 1;
        //cout << "Size: " << mod_d.size() << "\n";
        for(auto el : mod_d) {
            int f = el.first, s = el.second;
            cout << f << " " << 60 - f << "\n";
            ans += mod_d[(60 - f) % 60] * (((60 - f) % 60) == f ? s - 1 : s);
        }
        
        return ans / 2;
    }
};

Sample Input Test: [15, 63, 451, 213, 37, 209, 343, 319]

And the output is as follows:

3 57
15 45
19 41
29 31
31 29
33 27
37 23
41 19
43 17
45 15
57 3

The number of elements printed should be only 8 inside the loop, but with an unordered_map, the elements are much more.

The code that is not working well is below:

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        unordered_map<int, int> mod_d;
        
        for(auto el : time) {
            if(mod_d.count(el % 60) == 0) {
                mod_d[el % 60] = 1;
            }else mod_d[el % 60]++;
        }
        
        int ans = 0, i = 1;
        //cout << "Size: " << mod_d.size() << "\n";
        for(auto el : mod_d) {
            int f = el.first, s = el.second;
            cout << f << " " << 60 - f << "\n";
            ans += mod_d[(60 - f) % 60] * (((60 - f) % 60) == f ? s - 1 : s);
        }
        
        return ans / 2;
    }
};

The only difference is the usage of unordered_map instead of a map

And it prints the elements wrongly as:

19 41
43 17
37 23
33 27
31 29
29 31
3 57
41 19
15 45
41 19
3 57
29 31
31 29
57 3
33 27
37 23
43 17
17 43
19 41
23 37
27 33

Anyone knows why is this odd behavior happening?

Mohamed Ayman Naguib
  • 27
  • 3
  • 2
    please show the code that has the problem instead of the one that does not have it ([mcve]) – 463035818_is_not_an_ai Dec 23 '20 at 20:49
  • also include the output and the expected output – 463035818_is_not_an_ai Dec 23 '20 at 20:49
  • Alright will add them right now – Mohamed Ayman Naguib Dec 23 '20 at 20:51
  • The second for loop creates more elements in the map. maps and unordered maps, by definition, store their contents in different order, and it just so happens that with an unordered_map you end up iterating over the new elements in the map, as part of the same loop. With a regular map you don't. – Sam Varshavchik Dec 23 '20 at 20:51
  • Also please try to make your question self-contained, which means you need to tell us the exact problem you need to solve. – Some programmer dude Dec 23 '20 at 20:52
  • And you should take this as an opportunity to learn something competition sites doesn't teach (and honestly they barely teach anything except bad habits): **Debugging**. Using a *debugger* you can step through your code statement by statement while monitoring variables and their values to see what actually happens. – Some programmer dude Dec 23 '20 at 20:54
  • I have updated the question as per your suggestions, Thank you so much. I will try to use a debugger as well indeed. – Mohamed Ayman Naguib Dec 23 '20 at 20:57
  • 1
    in second loop try `map_d.at(...) ` instead of square brackets and see what happens – j.holetzeck Dec 23 '20 at 20:59
  • @j.holetzeck When I added a check if the `(60 - f) % 60)` is found and used `at()` the number of elements is indeed correct now :D. Can you please tell me why is that? – Mohamed Ayman Naguib Dec 23 '20 at 21:03
  • Alright I now understand, thank you so much all for the help. As per this link that shows the different ways to access a map, I see that using `[]` operator creates the elements if they are not there and that is my mistake. https://stackoverflow.com/questions/33236038/when-i-should-use-stdmapat-to-retrieve-map-element – Mohamed Ayman Naguib Dec 23 '20 at 21:06

1 Answers1

1

Alright I now understand, thank you so much all for the help. As per this link that shows the different ways to access a map, I see that using [] operator creates the elements if they are not there in the map and that is my mistake. When I should use std::map::at to retrieve map element

Fix

Checking if the element exist at first and using at() to access it

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        unordered_map<int, int> mod_d;

        for(auto el : time) {
            if(mod_d.count(el % 60) == 0) {
                mod_d[el % 60] = 1;
            }else mod_d[el % 60]++;
        }

        int ans = 0, i = 1;
        cout << "Size: " << mod_d.size() << "\n";
        for(auto el : mod_d) {
            int f = el.first, s = el.second;
            cout << f << " " << i++ << "\n";
            if(mod_d.count((60 - f) % 60) > 0) ans += mod_d.at((60 - f) % 60) * (((60 - f) % 60) == f ? s - 1 : s);
        }

        return ans / 2;
    }
};
Mohamed Ayman Naguib
  • 27
  • 3
  • Note that you can simplify your whole first loop to: `for(auto el : time) { mod_d[el % 60]++; }`. This'll work for the exact reason that your old code was failing :) – scohe001 Dec 23 '20 at 21:16
  • Yes, that is indeed correct and I had it like that at first. But, when it was acting odd, I thought this might be a problem xD. Thanks again for the suggestion :D :D – Mohamed Ayman Naguib Dec 23 '20 at 22:09