Why hash_map works in finding 4 values (at distinct positions) whose sum is x?

Revision en2, by I_love_Kim_Dahyun, 2020-09-13 22:01:04

problem link

SOLUTION — Geeks for Geeks

I have also seen william lin solve it using hash_map in his cses speedrun video on youtube.

But C++ STL unordered_map is a 1 to 1 mapping of key and value. So say x = 12, Now we could make x by doing (a1+a4) + (a2+a3) = 5 + 7. But let's say (a3+a4) = 7 as well , and as unordered_map records only the latest occurrence of 7, so we only have 7 at (a3+a4). As a4 is repeating in both (a1+a4) and (a3+a4), these are not distinct positions and we don't have an answer.

This is not a perfect example, because we can discover other good ways to make 12 if we check other possible combinations. And also a perfect example might not exist given that this is a well-known solution, I just wanted to convey my idea why unordered_map might fail and it is not all clear to me why it actually works for every possibility.

Tags hash_table, unordered_map


  Rev. Lang. By When Δ Comment
en2 English I_love_Kim_Dahyun 2020-09-13 22:01:04 3 Tiny change: 'st wanted convey my' -> 'st wanted to convey my'
en1 English I_love_Kim_Dahyun 2020-09-13 18:36:43 1074 Initial revision (published)