Friday, July 18, 2014

Find pairs of integers in an array that sum to a value

Problem

Design an algorithm to find all pairs of integers within an array which sum to a specified value.

Solution 

We have found a pair of elements in an array which sum upto a given number already, this is a known problem called 2-sum problem. We know we can solve this problem in O(n) time.

Let T be the sum.

Method 1 - Using Hash table solution
We can extend the same. We will add all the elements in the hash table. Now, for all elements we select element x, and check if hash table contains T-x and print it.

Method 2 - Sorting
  1. sort the array
  2. for each number in the array A(n), do a binary search to find the number A(x) such that A(n) + A(x) =T
Please refer the same post.

Reactions:

0 comments:

Post a Comment