Sort:  
  • Trending
    • [-]
     8 years ago (edited)

    My thought:

    As you iterate through the array, store the difference between the given number and array element in memory. If an element you come across in the array is in the set already, you've found a pair. Might be easier to see in code:

    (In java since that's what I primarily use)

        int[] arr = { 5, 10, 5, 15, 20, 5 };
    int n = 20;
    int count = 0;
    HashMap<Integer, Integer> diffs = new HashMap<>();
    for (Integer i : arr) {
        if (diffs.containsKey(i)) {
            count += diffs.get(i);
        }
        Integer found = diffs.getOrDefault(n - i, 0);
        diffs.put(n - i, ++found);
    }

    System.out.println("count: " + count);

    Note: I had to use a HashMap and not a HashSet because HashSet doesn't account for several of the same number in the array (eg. 5 which you see in my case above).

    Edit: I think I solved the wrong problem, since you specified all pairs and not the count of pairs. Dunno where that came from. Easy enough to fix though, you just store both numbers as you find them and output that instead.

    [-]
     8 years ago 

    Hi, I am the new curator for @math-trail, a community dedicated to promoting the best articles on mathematics in its widest sense, including educational and cultural aspects.

    I just upvoted your post - hope to see more in the future.

    If you like to write about mathematics, then please follow @math-trail and I will follow you back and look forward to see fresh new content.

    If you enjoy reading about mathematics, then please follow me so that you will receive the best content in your personal feed.

    I am not a bot! Thanks!

    $0.00
      Reply