Question

Problem Definition:

Problem: Given an array of integers print all pairs of integers a and b where a + b is equal to a given number.

For example, consider the following array and suppose we want to find all pairs of integers a and b where a + b = 16

A= [ 10, 4, 6, 15, 3, 5, 1, 13]

The following are pairs that sum to 16:

13, 3

6, 10

15, 1

Your program should print these pairs.

A poor Solutions:

There are several solutions to this problem. The most straightforward (but inefficient ) solution is to set up a nested loop structure that goes over the elements of the array one by one and for each element performs a sequential search on the entire array. The running time for this algorithm is quadratic due to the nested loop structure and the sequential search for each array element.

What you need to do for this assignment

When the size of the array is very large then the quadratic algorithm may be too slow to be useful. There are a number of strategies that can be employed to reduce the running time, and at this point we have covered enough topics to design a more efficient algorithm. Based on the material covered thus far in this course, design and implement a more efficient algorithm for this problem.

Hint, you might find it helpful to first sort the array. As for the searching aspect, there are two ways you can go about it that will be efficient and both solutions are valid. One involves utilizing the Binary Search while the other does not involve searching at all.

No additional libraries may be used. All code must be implemented by you or else you will receive a 0 for the assignment. This includes the Arrays class.

Your algorithm must at most have a running time of O(nlogn) where n is the number of elements in the array.

The framework for your algorithm should satisfy the following criteria:

1. The SumPairs class is given to you with a main method that will produce test code for you.
2. You just need to implement the printPairs method. This prints the pairs of numbers that sum to some given value.
3. You may implement any additional methods to help you solve the problem.
4. The efficiency of your algorithm must at most be O(n log n).

It is important that you adhere to the framework specification above to facilitate testing of your program.

What you need to turn in

1. Your SumPairs.java file with a proper implementation of printPairs and any other methods you implemented.
2. Include a document file with an explanation of your algorithm in your own words. You may use pseudocode to break down your algorithm. Include an explanation of your efficiency.
3. Include a document with test inputs you create. You can change the test input in main. Make sure to include the tests for when there are duplicate pairs, no pairs, and many pairs.

public class SumPairs {

   //-----Implement your algorithm here------
   public static void printPairs(int arr[], int sum) {
       return 0;
   }
  
   //-----End Student Implementation-----
  
   public static void main(String[] args) {
       int arr[] = {
           16, 53, 89, 28, 72, 51, 3, 26, 99,
           85, 57, 1, 92, 96, 2, 56, 11, 41,
           3, 80, 16, 41, 79, 85, 78, 53, 45,
           18, 91, 82, 39, 26, 23, 64, 32, 75,
           70, 11, 48, 45, 76, 53, 14, 67, 2,
           42, 92, 69, 24, 23, 78, 27, 100, 60,
16, 94, 65, 77, 45, 37, 98, 56, 6, 6,
3, 94, 64, 26, 50, 56, 74, 24, 37, 67,
74, 48, 35, 40, 42, 90, 15, 50, 16, 36,
42, 70, 4, 62, 39, 16, 53, 89, 89, 38, 3,
53, 35, 20, 17, 44
       };
      
       int sumToCheck = 58;
       printPairs(arr, sumToCheck);
   }

}

Answer 1

Below is the complete working code in Java. If you face any difficulty while understanding the code, Please let me know in the comments.

Appraoch:

This appraoch has a time complexity of O(nlogn). Here we are using the Two pointers technique to find the pairs that sums to a given value.

Note: We can't use QuickSort here as it has worst case time complexity of O(n*n). But we want our solution to work in O(nlogn) time. So using MergeSort will be better choice here.

Two Pointers:

It works only for sorted arrays. In this technique, We use two pointers, one referencing at the first element of the sorted array and other representing the last element. After that we run a loop until the first pointer reference index is less than the one referencing the last of array. Then we add the elements at both the pointers. If their sum is less than the target sum, then we shift the start pointer towards right and if their sum is more than the target sum, we shift the last pointer towards left so that we can get closer to the target sum. We repeat this process until the sum is equal to the target sum.

Code:

public class SumPairs {
  
// merge method to merge the sub division of array
public static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
int leftSize = left.length, rightSize = right.length;
  
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j])
arr[k++] = left[i++];
else
arr[k++] = right[j++];
}
  
while (i < leftSize) {
arr[k++] = left[i++];
}
while (j < rightSize) {
arr[k++] = right[j++];
}
}
  
// mergeSort method to sort the array
public static void mergeSort(int[] arr, int n) {
if (n < 2) return;
  
int mid = n / 2;
int[] left = new int[mid];
int[] right = new int[n - mid];

for (int i = 0; i < mid; i++)
left[i] = arr[i];
  
for (int i = mid; i < n; i++)
right[i - mid] = arr[i];
  
mergeSort(left, mid);
mergeSort(right, n - mid);
merge(arr, left, right);
}
  
//-----Implement your algorithm here------
public static void printPairs(int arr[], int sum) {

// Sort the given array in ascending order using mergeSort
mergeSort(arr, arr.length);

// Create pointers at start and end of an array
int low = 0, high = arr.length - 1;

while (low < high) {
// if both pointers equals sum, it means we have found a pair
// So print the pair and increase lower index and decrease higher index
if (arr[low] + arr[high] == sum) {
System.out.println(arr[low] + " " + arr[high]);
}
// if arr[low] + arr[high] > sum, it means pair is left to high
// so decrease high
if (arr[low] + arr[high] > sum) {
high--;
}
// if arr[low] +arr[high] <sum, it means we need to increase low
else {
low++;
}
}
}
  
   public static void main(String[] args) {
  
   int arr[] = {
16, 53, 89, 28, 72, 51, 3, 26, 99,
85, 57, 1, 92, 96, 2, 56, 11, 41,
3, 80, 16, 41, 79, 85, 78, 53, 45,
18, 91, 82, 39, 26, 23, 64, 32, 75,
70, 11, 48, 45, 76, 53, 14, 67, 2,
42, 92, 69, 24, 23, 78, 27, 100, 60,
16, 94, 65, 77, 45, 37, 98, 56, 6, 6,
3, 94, 64, 26, 50, 56, 74, 24, 37, 67,
74, 48, 35, 40, 42, 90, 15, 50, 16, 36,
42, 70, 4, 62, 39, 16, 53, 89, 89, 38, 3,
53, 35, 20, 17, 44
};
  
int sumToCheck = 58;
printPairs(arr, sumToCheck);

   }
}

}

Screenshots:

Output:

Edit: Complete solution without using any Java library.