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

Write a C program that, given an array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x.

Interview version:

Given a number k and an array of integers A. find two integers in the array which sum to k. Do this in linear time and O(n) space, iterating over the array exactly once. 
variation : Now do this in constant space and O(n log n) time.

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

Time Complexity: Depends on what sorting algorithm we use. If we use Merge Sort or Heap Sort then (-)(nlogn) in worst case. If we use Quick Sort then O(n^2) in worst case.

Auxiliary Space : Again, depends on sorting algorithm. For example auxiliary space is O(n) for merge sort and O(1) for Heap Sort.

Example:
Let Array be {1, 4, 45, 6, 10, -8} and sum to find be 16

Sort the array
A = {-8, 1, 4, 6, 10, 45}

Initialize l = 0, r = 5
A[l] + A[r] ( -8 + 45) > 16 => decrement r. Now r = 10
A[l] + A[r] ( -8 + 10) < 2 => increment l. Now l = 1
A[l] + A[r] ( 1 + 10) < 16 => increment l. Now l = 2
A[l] + A[r] ( 4 + 10) < 14 => increment l. Now l = 3
A[l] + A[r] ( 6 + 10) == 16 => Found candidates (return 1)

Note: If there are more than one pair having the given sum then this algorithm reports only one. Can be easily extended for this though.

Code:

import java.io.*;
import java.util.*;
public class Sum2 
{
	// Global variables 
	static int len=0,sum=0;  
	private static int array[] =new int[len]; // initialization of array length as 0
	
	public static void main(String args[]) throws NumberFormatException, IOException
	{	
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		System.out.println("Enter length of array");
		len =Integer.parseInt(br.readLine()); // take length of array from user  
		
		setArray(Arrays.copyOf(getArray(), getArray().length + len));  // reinitialize array to given length
		
		System.out.println("Enter elements:"); // takes input
		for(int i=0;i<len;i++)
			getArray()[i]=Integer.parseInt(br.readLine());
		
		System.out.println("Enter sum:");
		sum =Integer.parseInt(br.readLine());
		
		Sum2 s = new Sum2(); 
		Quicksort q = new Quicksort();
		
		q.sort(0,getArray().length-1); // perform sorting
		s.find2sum(); // to find pair in A[] with sum as x
	}
	
	/***************************************************************************
	    *  Method for finding pair in A[] with sum as x
	 ***************************************************************************/
	void  find2sum()
	{
		System.out.println("Output pairs:");
	    int lo = 0;
	    int hi = array.length-1; 
	    while (lo < hi)
	    {
	        if((array[lo] + array[hi]) == sum)
	        	System.out.println("Pair with given sum "+sum+" is (" + array[lo]+", "+array[hi]+")");
	        if((array[lo] + array[hi]) < sum)
	 	        lo++;
	 	     else 
	 	        hi--;
	         }	        	        	         
	}	
	
	/***************************************************************************
	    * functions to access array
	 ***************************************************************************/	
	public static int[] getArray() {
		return array;
	}
	
	public static void setArray(int array[]) {
		Sum2.array = array;
	}
}
/***************************************************************************
 *  QuickSort Algorithm
***************************************************************************/
class Quicksort 
{
	static Quicksort q1= new Quicksort();
	
	void sort(int low,int high) // Check whether an array is empty
	{		
		if(high<=low)
			return ;
		int j=partition(low,high);
		// recursive call to quickSort() method 
		sort(low,j-1);
		sort(j+1,high);
	}
	
	int partition(int low,int high)
	{
		int i=low;
		//System.out.println(s1.getArray()[low]);
		int j=high+1;
		int pivot=Sum2.getArray()[low]; 
		while(true)
		{
			while(Sum2.getArray()[++i]<pivot) // find item on low to swap
				if (i == high) break; // Boundary case
			
			while(Sum2.getArray()[--j]>pivot)  // find item on high to swap
				if (j == low) break;   // Boundary case
			// check if pointers cross
			if (i >= j) break;
				q1.exchange(i,j);
			
		}
		exchange(low, j);
		return j;
	}

	void exchange(int i,int j)
	{	
		int temp=Sum2.getArray()[i];
		Sum2.getArray()[i]=Sum2.getArray()[j];
		Sum2.getArray()[j]=temp;
	}

}

/***************************************************************************
OUTPUT: 

Enter length of array
8
Enter elements:
55
181
45
69
-81
3145
31
801
Enter sum:
100
Output pairs:
Pair with given sum 100 is (-81, 181)
Pair with given sum 100 is (31, 69)
Pair with given sum 100 is (45, 55)
***************************************************************************/

Or

View on Github

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]]

Code:

//Implementation using Hashing
import java.io.*;
import java.util.*;

public class Sum2Hash 
{
	public static void main(String args[]) throws NumberFormatException, IOException
	{
		Sum2Hash s=new Sum2Hash();
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in)); 
		System.out.println("Enter array length");
		int len =Integer.parseInt(br.readLine());
		
		
		int array[]=new int[len];
		System.out.println("Enter Element");
		for(int i=0;i<array.length;i++)
			array[i]=Integer.parseInt(br.readLine());
	
		System.out.println("Enter sum:");
		int sum =Integer.parseInt(br.readLine());
		
		s.findpairs(array, sum);
	}

	void findpairs(int array[],int sum)
    	{
		 Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();
 
        	for (int i=0; i<array.length; i++)
        	{
        		if(pairs.containsKey(array[i]))
	            		System.out.println("Pair with given sum "+sum+" is ("+array[i] +", "+ pairs.get(array[i])+")");
	        	else
	            		pairs.put(sum-array[i], array[i]);
        	}
    	}
}

/***************************************************************************
OUTPUT: 

Enter array length
8
Enter Element
55
181
45
69
-81
3145
31
801
Enter sum:
100
Pair with given sum 100 is (45, 55)
Pair with given sum 100 is (-81, 181)
Pair with given sum 100 is (31, 69)
***************************************************************************/

Or

View on Github

Time Complexity: O(n)
Auxiliary Space: O(k) where k is range of integers.

[Credit: Above examples are taken from geeksforgeeks .]