Java Programming – check for pair in A[] with sum as x

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

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.

Implementation:

Java Program
// Java solution for above problem
class Main
{
static boolean hasArrayTwoCandidates(int A[], int arr_size, int sum)
{
int l, r;

/* Sort the elements */
sort(A, 0, arr_size-1);

/* Now look for the two candidates
in the sorted array*/
l = 0;
r = arr_size-1;
while (l < r)
{
if(A[l] + A[r] == sum)
return true;
else if(A[l] + A[r] < sum)
l++;
else // A[i] + A[j] > sum
r--;
}
return false;
}

//main function
public static void main(String args[])
{
int A[] = {1, 4, 45, 6, 10, -8};
int n = 16;
int arr_size = 6;

if( hasArrayTwoCandidates(A, arr_size, n))
System.out.println("Array has two "+
"elements with sum 16");
else
System.out.println("Array doesn't have "+
"two elements with sum 16 ");

}

/* Below functions are only to sort the
array using QuickSort    */

/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
static int partition(int arr[], int low, int high)
{
int pivot = arr[high];

// index of smaller element
int i = (low-1);
for (int j=low; j<=high-1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;

// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;

return i+1;
}

/* The main function that
implements QuickSort()
arr[] --> Array to be sorted,
low  --> Starting index,
high  --> Ending index */
static void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);

// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
}

Output:

Array has two elements with the given sum

METHOD 2 (Use Hash Map)
Thanks to Bindu for suggesting this method and thanks to Shekhu for providing code.
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]]

Implementation:

Java Program
// Java implementation using Hashing
import java.io.*;

class PairSum
{
private static final int MAX = 100000; // Max size of Hashmap

static void printpairs(int arr[],int sum)
{
// Declares and initializes the whole array as false
boolean[] binmap = new boolean[MAX];

for (int i=0; i<arr.length; ++i)
{
int temp = sum-arr[i];

// checking for condition
if (temp>=0 && binmap[temp])
{
System.out.println("Pair with given sum " +
sum + " is (" + arr[i] +
", "+temp+")");
}
binmap[arr[i]] = true;
}
}

// Main to test the above function
public static void main (String[] args)
{
int A[] = {1, 4, 45, 6, 10, 8};
int n = 16;
printpairs(A,  n);
}
}

Time Complexity: O(n)
Output:

Pair with given sum 16 is (10, 6)

Auxiliary Space: O(R) where R is range of integers.

See also  Java Programming - Construct an array from its pair-sum array

If range of numbers include negative numbers then also it works. All we have to do for negative numbers is to make everything positive by adding the absolute value of smallest negative integer to all numbers. 