2

I am referring to the following question that was asked before. And, I am interested in the following solution mentioned over there:

enter image description here

I am trying to understand it for the following integer array and I am lost after iteration #5 as shown below :

Let's say our integer array is : {1,2,3,4,8,9,10} and we should print those pairs for which sum is equal to 12. So, I tried to analyze step by step what happens if we apply the above mentioned approach:

                             Key             Value   
Iteration 1 : i = 0       (12-1) = 11          1 
Iteration 2 : i = 1       (12-2) = 10          2
Iteration 3 : i = 2       (12-3) = 09          3
Iteration 4 : i = 3       (12-4) = 08          4
Iteration 5 : i = 4       // pairs.containsKey is true here so printing 
                             input[i] = 8

Could any one explain me why are we printing input[i] = 08 and pairs.get(input[i])) which is also 08 in iteration #5 above?

Secondly I didn't find anything online as far as codaddict's algorithm is concerned.

Community
  • 1
  • 1
John
  • 1,180
  • 5
  • 21
  • 48
  • Wow, looks like i owe some explanation here ! Implementation is a bit different to codeaddict user's algorithm. – Rambo7 Oct 28 '15 at 22:15

3 Answers3

1

When i==4, input[i] == 8, but pairs.get(input[i])) is pairs.get(8), which is equal to 4, since in the previous iteration, when i was 3, we performed pairs.put(k-input[i],input[i]), or in order words pairs.put(12-4,4).

Eran
  • 374,785
  • 51
  • 663
  • 734
1

I think you need to understand the algorithm at first.We want to find the pair of number in array where sum is K.

If there are two number (x,y) in array where sum is K, then 

x+y = k,
or y = k-x.

Now for a number x, we are mapping x to key (k-x).

Then for another number y, if we can find that y is in map, that means, there was a number x for which (k-x) was mapped which is equal to y. Now from the map we can find the original x and print it.

sabbir
  • 438
  • 3
  • 10
  • Could you tell me from where I can read codaddicts's algorithm? – John Oct 22 '15 at 07:28
  • Actually codaaddicts is an user of stackoverflow. His answers was written in python in that question and was accepted. His algorithm in python was referred as codaaddicts algorithm – sabbir Oct 22 '15 at 07:31
  • Good that you clarified. I thought he has something to do with this algorithm. – John Oct 22 '15 at 07:39
1

Have had a brief look at the answer you quoted. To answer your question,

why are we printing input[i] = 08 and pairs.get(input[i])) which is also 08 in iteration #5 above?

it is printing input[i] which is 8, and pairs.get(input[i]) which means pairs.get(8) which is 4.

Something you need to know is, that piece of Java code is NOT implementing Codaddict's logic. It looks a bit a like but it is simply doing something different: Codaddict is storing the input value as key, and index as value, while that Java implementation is storing (sum-value) as key and value as value.

That Java implementation is not sane. What it is doing can be simplified to:

public static void printSumPairs(int []input, int sum){
    Set<Integer> previousInts = new HashSet<>();

    for (int i : input) {
        if (previousInts.contains(sum - i)) {
             System.out.print("" + (sum - i) + ", " + i);
        } else {
             previousInts.add(i);
        }
    }
}

This essentially achieve the same result as that Java impl, and (I believe) is much easier to understand.

Doesn't work well with duplicated numbers though (which is the same for the original Java impl). However having a logic that handles number duplication is actually easy.

Adrian Shum
  • 36,850
  • 10
  • 77
  • 125
  • 1
    Thanks for the explanation. Sabbir clarified that Codaddict is a username on Stackoverflow and not an author of some algorithm. I was totally confused and tired of searching online who was codaddict. – John Oct 22 '15 at 07:41