Determine whether or not there exist two elements in an array whose sum is exactly X?

Question

Given an array A[] of N elements and a number x, check for pair in A[] with sum as x ?

Method 1 = Sorting which gives O(n lg n).

Method 2 = Using hash table which gives O(n) .

I am having a doubt in method 2, that what if chaining is used , then for every element we have to search in list for its complement , which can yield O(n^2) in worst case because of chaining .

I think it will work only when range of integers is given , so that we can have hashtable without chaining which gives O(n) . Am i right ?

How big is that array and how often do you want to check it? In other words, how important *is* performance in this particular case? — Hans Keﬆing, Aug 31 '16 at 07:06
Possible duplicate of [Find a pair of elements from an array whose sum equals a given number](http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number) — Ruud Helderman, Aug 31 '16 at 07:07
I have edited now . I just want to know , that is range useful or will it work without range . — Garrick, Aug 31 '16 at 07:08

score 0 · Answer 1 · answered Aug 31 '16 at 07:26

0

You can try the following approach ->

hash all elements in A[], like (key, value) = (A[i],true) 

for all elements in A[]:
    if hash(x-A[i])=true: it exists

answered Aug 31 '16 at 07:26

jbsu32

966
1
9
29

score 0 · Answer 2 · answered Aug 31 '16 at 07:37

You are right about hashtable that O(n) is not the WORST CASE guaranteed complexity. However, with a reasonable hash function, the worst case should rarely happen.

And of course, if a small enough upper bound is given on the range of numbers, you can just use normal array to do the trick.

score 0 · Answer 3 · answered Feb 19 '19 at 20:08

O(N) solution which uses hashmap to maintain the element Vs its frequency. Frequency is maintained so as to make it work for duplicate array elements case.

public static boolean countDiffPairsUsingHashing(int[] nums, int target) {

        if (nums != null && nums.length > 0) {
            HashMap<Integer, Integer> numVsFreq = new HashMap<Integer, Integer>();
            for (int i = 0; i < nums.length; i++) {
                numVsFreq.put(nums[i], numVsFreq.getOrDefault(nums[i], 0) + 1);   
            }

            for (int i = 0; i < nums.length; i++) {
                int diff = target - nums[i];
                numVsFreq.put(nums[i], numVsFreq.get(nums[i]) - 1);

                if (numVsFreq.get(diff) != null && numVsFreq.get(diff) > 0) {
                    return true;
                }
                numVsFreq.put(nums[i], numVsFreq.get(nums[i]) + 1);
            }
        }
        return false;
    }

Determine whether or not there exist two elements in an array whose sum is exactly X?

3 Answers3