checking if 2 numbers of array add up to I

Question

I saw a interview question as follows: Give an unsorted array of integers A and and an integer I, find out if any two members of A add up to I.

any clues?

time complexity should be less

Answer 1

Insert the elements into hashtable.

While inserting x, check if I-x already exists. O(n) expected time.

Otherwise, sort the array ascending (from index 0 to n-1). Have two pointers, one at max and one at min (call them M and m respectively).

If a[M] + a[m] > I then M-- 
If a[M] + a[m] < I then m++
If a[M] + a[m] == I you have found it
If m > M, no such numbers exist.

Answer 2

For example, loop and add possible number to set or hash and if found, just return it.

>>> A = [11,3,2,9,12,15]
>>> I = 14
>>> S = set()
>>> for x in A:
...     if x in S:
...         print I-x, x
...     S.add(I-x)
...
11 3
2 12
>>>

Answer 3

If you have the range which the integers are within, you can use a counting sort-like solution where you scan over the array and count an array up. Ex you have the integers

input = [0,1,5,2,6,4,2]

And you create an array like this:

count = int[7]

which (in Java,C# etc.) are suited for counting integers between 0 and 6.

foreach integer in input
    count[i] = count[i] + 1

This will give you the array [1,1,2,0,1,1,1]. Now you can scan over this array (half of it) and check whether there are integers which adds up to i like

for j = 0 to count.length - 1
    if count[j] != 0 and count[i - j] != 0 then // Check for array out-of-bounds here
         WUHUU! the integers j and i - j adds up

Overall this algorithm gives you O(n + k) where n is from the scan over the input of length n and k is the scan over the count array of length k (integers between 0 and k - 1). This means that if n > k then you have a guaranteed O(n) solution.

Answer 4

1. sort the array
2. for each element X in A, perform a binary search for I-X. If I-X is in A, we have a solution.

This is O(nlogn).

If A contains integers in a given (small enough) range, we can use a trick to make it O(n):

1. we have an array V. For each element X in A, we increment V[X].
2. when we increment V[X] we also check if V[I-X] is >0. If it is, we have a solution.

Answer 5

public static boolean findSum2(int[] a, int sum) {
        if (a.length == 0) {
            return false;
        }
        Arrays.sort(a);


        int i = 0;
        int j = a.length - 1;
        while (i < j) {
            int tmp = a[i] + a[j];
            if (tmp == sum) {
                System.out.println(a[i] + "+" + a[j] + "=" + sum);
                return true;
            } else if (tmp > sum) {
                j--;
            } else {
                i++;
            }
        }
        return false;
}

Answer 6

O(n) time and O(1) space

If the array is sorted there is a solution in O(n) time complexity.

Suppose are array is array = {0, 1, 3, 5, 8, 10, 14}

And our x1 + x2 = k = 13, so output should be= 5, 8

1. Take two pointers one at start of array, one at end of array
2. Add both the elements at ptr1 and ptr2 array[ptr1] + array[ptr2]
3. if sum > k then decrement ptr2 else increment ptr1
4. Repeat step2 and step3 till ptr1 != ptr2

Same thing explained in detail here. Seems like an Amazon interview Question http://inder-gnu.blogspot.com/2007/10/find-two-nos-in-array-whose-sum-x.html

Answer 7

This might be possible in the following way: Before putting the elements into the hashmap, you can check if the element is greater than the required sum. If it is, you can simply skip that element, else you can proceed with putting it into the hashmap. Its a slight improvement on your algorithm, although the overall time still remains the same.

Answer 8

This can be solved using the UNION-FIND algorithm, which can check in constant time whether an element is into a set.

So, the algorithm would be so :

foundsum0 = false;
foreach (el: array) {
    if find (-x): foundsum0 = true;
    else union (x);
}

FIND and UNION are constant, O(1).

Answer 9

here is a O(n) solution in java using O(n) extra space. This uses hashSet to implement it

http://www.dsalgo.com/UnsortedTwoSumToK.php

Answer 10

Here is a solution witch takes into account duplicate entries. It is written in javascript and assumes array is sorted. The solution runs in O(n) time and does not use any extra memory aside from variable. Choose a sorting algorithm of choice. (radix O(kn)!) and then run the array through this baby.

var count_pairs = function(_arr,x) {
  if(!x) x = 0;
  var pairs = 0;
  var i = 0;
  var k = _arr.length-1;
  if((k+1)<2) return pairs;
  var halfX = x/2; 
  while(i<k) {
    var curK = _arr[k];
    var curI = _arr[i];
    var pairsThisLoop = 0;
    if(curK+curI==x) {
      // if midpoint and equal find combinations
      if(curK==curI) {
        var comb = 1;
        while(--k>=i) pairs+=(comb++);
        break;
      }
      // count pair and k duplicates
      pairsThisLoop++;
      while(_arr[--k]==curK) pairsThisLoop++;
      // add k side pairs to running total for every i side pair found
      pairs+=pairsThisLoop;
      while(_arr[++i]==curI) pairs+=pairsThisLoop;
    } else {
      // if we are at a mid point
      if(curK==curI) break;
      var distK = Math.abs(halfX-curK);
      var distI = Math.abs(halfX-curI);
      if(distI > distK) while(_arr[++i]==curI);
      else while(_arr[--k]==curK);
    }
  }
  return pairs;
}

I solved this during an interview for a large corporation. They took it but not me. So here it is for everyone.

Start at both side of the array and slowly work your way inwards making sure to count duplicates if they exist.

It only counts pairs but can be reworked to

• find the pairs
• find pairs < x
• find pairs > x

Enjoy and don't forget to bump if its the best solution!

Answer 11

Split the array into two groups <= I/2 and > I/2. Then split those into <= I/4,>I/4 and <= 3I/4,>3I/4 And repeat for log(I) steps and check the pairs joining from the outside e.g 1I/8<= and >7I/8 and if they both contain at least one element then they add to I. This will take n.Log(I) + n/2 steps and for I

Answer 12

for nlogn : Sort the array and for each element [0<=j<len A] , subtract i-A[j] and do a binary search for this element in sorted array.

hashmap (frequency of no, number) should work in O(n).

Answer 13

for each ele in the array
  if (sum - ele) is hashed and hashed value is not equal to index of ele
    print ele, sum-ele
  end-if
  Hash ele as key and index as value
end-for

Answer 14

PERL implementation to detect if a sorted array contains two integer that sum up to Number

my @a = (11,3,2,9,12,15);
my @b = sort {$a <=> $b} @a;

my %hash;
my $sum = 14;
my $index = 0;
foreach my $ele (@b) {
    my $sum_minus_ele = $sum - $ele;
    print "Trace: $ele :: $index :: $sum_minus_ele\n";
    if(exists($hash{$sum_minus_ele}) && $hash{$sum_minus_ele} != $index ) {
        print "\tElement: ".$ele." :: Sum-ele: ".$sum_minus_ele."\n";
    }
    $hash{$ele} = $index;
    $index++;
}

Answer 15

An implementation in python

def func(list,k):
temp={} ## temporary dictionary
for i in range(len(list)):
    if(list[i] in temp): ## if temp already has the key just increment its value
        temp[list[i]] +=1
    else:  ## else initialize the key in temp with count as 0
        temp[list[i]]=0 

    if(k-list[i] in temp and ((k/2 != list[i]) or temp[list[i]]>=1)): ## if the corresponding other value to make the sum k is in the dictionary and its either not k/2 or the count for that number is more than 1
        return True

return False

Input: list is a list of numbers (A in the question above)...
k is the sum (I in the question above)....

The function outputs True if there exist a pair in the list whose sum is equal to k and False otherwise...

I am using a dictionary whose key is the element in the array(list) and value is the count of that element(number of times that element is present in that list). Average running time complexity is O(n).

This implementation also takes care of two important edge cases:

• repeated numbers in the list and
• not adding the same number twice.