**Question 1**

Given an array of integers, you must find a pair within the array that sums up to a given sum. We assume the array is unsorted.

For example:

**Input: **

Array A = {4, 9, 7, 3, 6, 8}

Sum = 11

**Output: **

Pair found at 0 and 2 (4 + 7)

Pair found at 3 and 5 (3 + 8)

**Solution 1: Inefficient Solution (Quadratic time)**

In this solution, we loop through the array and for each element, we calculate the sum with every other element and compare with the given sum. If the sum equals the given sum. We output the indexes.

The Java program is given below:

//Question 1: Given an unsorted array of integers // find a pair of integers with the given sum in it package examples; public class FindPairSum1{ public static void findPair1(int A[], int sum) { //loop until element before the last for(int i = 0; i< A.length-1; i++) { //loop until the last element for(int j = i+1; j < A.length; j++) { //if given sum is found, print the indexes if(A[i] + A[j] == sum) { System.out.println("Pair found at " + i + " and " + j); } } } }//End of findPair1 public static void main(String args[]) { int ar[] = {3,5,2,8,0,1,11,7}; int sum = 10; findPair1(ar, sum); }//End of main }

**Solution 1:** Inefficient Solution – Quadratic Time

**Solution 2: Start by Sorting (nlog(n) time)**

In this solution, we first sort the array. As such, the largest elements are are the end of the array while the smallest elements are at the beginning of the array. Then we use two iterators. The first counting from the beginning of the array while the second counting from the end of the array.

For each iteration, we calculate the sum to check if it equals the given sum

The Java program is given below.

Note: The index returned with this method is the index of the elements in the sorted array which is not the same as the indexes in the original array.

//findPair2: Sorts the array. Maintain two indices of the two end-points //Complexity: O(nlogn) package examples; import java.util.Arrays; public class FindPairSum2 { public static void findPair2 (int A[], int sum) { Arrays.sort(A); //First sort the array int low = 0; int high = A.length - 1; while(low < high) { if(A[low] + A[high] == sum) { System.out.println("Sum found are " + A[low] + " and " + A[high]); low++; } else if(A[low] + A[high] < sum) { low = low + 1; } else { high = high - 1; } } //end of while loop } public static void main(String[] args) { int ar[] = {3,5,2,8,0,1,11,7}; int sum = 10; findPair2(ar, sum); } }

Solution 2: Maintain two indexes

**Solution 3 – Use of HashMap (Linear time O(n))**

In this solution, we iterate though the array just once and store each element in a hash set.. For each element, we would check if the complement of the element is already in the hashset. If it is there, then we have a sum. If it is not there then we insert it.

The Java implementation is given below.

//Find pair with given sum using a hashma[ package examples; import java.util.HashMap; import java.util.Map; public class FindPairSum3 { public static void findPair(int A[], int sum) { Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i< A.length; i++) { //if complement is already in map, print the pair if(map.containsKey(sum-A[i])) { System.out.println("Pair found at " + map.get(sum-A[i]) + " and " + i); } map.put(A[i], i); }//end of for }//end for function public static void main(String[] args) { int ar[] = {3, 20, 5, 6,1,9, 7, 22}; int sum = 29; findPair(ar, sum); } }

**Solution 3** : Using a HashMap