Legend_of_Azkaban's blog

Why hash_map works in finding 4 values (at distinct positions) whose sum is x?
By Legend_of_Azkaban, history, 4 years ago, In English

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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 13   Vote: I like it +8 Vote: I do not like it

I believe the intuition is exactly that. Map stores the rightmost occurence and you iterate pairs left to right

Let's assume that four numbers that we seek are located in the array as

A.......B.......C......D

Obviously hashmap is going to store (C+D) and the first pair you discover in the second nested loop is (A+B)

The problem with your example is that we don't actually care about a1 + a4 if a1 + a2 + a3 + a4 == 12. Yes, this pair maybe fruitless, but we're not even going to reach it. We will first encounter a1 + a2 and retrieve a3 + a4 from the hashmap.

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

    Thanks for the help. The one fact that we are always going to find $$$(A,B)$$$ first and retrieve $$$(C,D)$$$ covers it. If $$$(C,D)$$$ collides with $$$(A,B)$$$, it never was an answer in the first place. And if there are other pairs colliding with $$$(A,B)$$$ but equal to $$$C+D$$$, they are going to be replaced by $$$(C,D)$$$ in the unordered_map anyway as $$$(C,D)$$$ occurs late.

    → Reply