CareerCup

METHOD 1 (Use Sorting)

Algorithm:

hasArrayTwoCandidates (A[], ar_size, sum)
1) Sort the array in non-decreasing order.
2) Initialize two index variables to find the candidate
elements in the sorted array.
(a) Initialize first to the leftmost index: l = 0
(b) Initialize second the rightmost index: r = ar_size-1
3) Loop while l < r.
(a) If (A[l] + A[r] == sum) then return 1
(b) Else if( A[l] + A[r] < sum ) then l++
(c) Else r--
4) No candidates in whole array - return 0



METHOD 2 (Use Hash Map)

This method works in O(n) time if range of numbers is known.
Let sum be the given sum and A[] be the array in which we need to find pair.

1) Initialize Binary Hash Map M[] = {0, 0, …}
2) Do following for each element A[i] in A[]
(a) If M[x - A[i]] is set then print the pair (A[i], x – A[i])
(b) Set M[A[i]]

public static void findNumber(int [] arr, int sumvalue) {
Map hash = new HashMap<Integer, Integer>();
for(int i=0; i< arr.length; i++) {
if(hash.get(arr[i]) == null) {
int x = sumvalue - arr[i];
hash.put(arr[i], x);
if(hash.get(x) != null) {
System.out.println("The two numbers - " + arr[i] + " and " + x);
}

}
}

}

// Sort the array first ..

int arr[] = {-2,0,1,2,3,6,10,19,21,23,43};

int start=0, end = arr.length-1;
int x= 0;

while (start<end) {

if(arr[start]+arr[end]<x)
start++;
else if(arr[start]+arr[end]>x)
end--;
else if(arr[start]+arr[end]==x){
System.out.println("pair " + arr[start] + " " + arr[end]);
break;
}
}

// nlogn solution

METHOD 1 (Use Sorting)

Algorithm:

hasArrayTwoCandidates (A[], ar_size, sum)
1) Sort the array in non-decreasing order.
2) Initialize two index variables to find the candidate
elements in the sorted array.
(a) Initialize first to the leftmost index: l = 0
(b) Initialize second the rightmost index: r = ar_size-1
3) Loop while l < r.
(a) If (A[l] + A[r] == sum) then return 1
(b) Else if( A[l] + A[r] < sum ) then l++
(c) Else r--
4) No candidates in whole array - return 0



METHOD 2 (Use Hash Map)

This method works in O(n) time if range of numbers is known.
Let sum be the given sum and A[] be the array in which we need to find pair.

1) Initialize Binary Hash Map M[] = {0, 0, …}
2) Do following for each element A[i] in A[]
(a) If M[x - A[i]] is set then print the pair (A[i], x – A[i])
(b) Set M[A[i]]

what if they want all the pairs ??

/*
 * find all pairs of numbers that sum up to k
 
 * 2341,5 -> {(2,3), (4,1)}
 * 2222,4 -> {(2, 2), (2, 2), (2, 2), (2, 2), (2, 2), (2, 2)}
 * 2, 4 -> {}
 */
 
 void find_sum_pairs(int* vec, int n, int k)
 {
    qsort(vec, n, sizeof(int)); //O(nlog(n))
    int left, right;
    left = 0;
    right = n - 1;
    while(left < right)
    {
        if (vec[left] + vec[right] == k)
        {
            printf("(%d, %d)\n", left, right);
            for (int r = right - 1; r > left; r--)
            {
                if (vec[r] == vec[right])
                {
                    printf("(%d, %d)\n", left, r);
                }
            }
            left++;        
        }
        else if (vec[left] + vec[right] < k)
        {
            left++;
        }
        else
        {
            right--;
        }
    }
 }