Problem Definition:
Problem: Given an array of integers find 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 = 3
A = [10, 4, 6, 16, 1, 6, 12, 13]
Then your method should return the following pairs:
4, 1
15, 12
13, 10
A poor solution:
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.
Your algorithm must on average 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:
public Pair[] findPairs(int array[], int diff)
It is important that you adhere to the framework specification above to facilitate testing of your program.
Additional Information
What you need to turn in
Briefly describe your algorithm and determine the time efficiency of it. Don’t just say, for example, that my algorithm is O(nlogn), but explain how you got that time efficiency. Remember, don’t evaluate your code. That takes too long and will give you a headache. Instead, try to conceptualize how you are solving the problem and determine the Big-O that way. Pen and paper will help with this.
import assignment.utility.ArrayUtils;
public class DifferencePairs {
// Implement your sorting algorithm here. Must be either
// * merge sort
// * quick sort
// * radix sort
private static void sort(int arr[]) {
}
public static Pair[] findPairs(int array[], int diff) {
return null;
}
}
public class Pair {
private int first;
private int second;
public Pair(int first, int last)
{
this.first = first;
this.second= last;
}
public int getFirst() {
return first;
}
public int getSecond() {
return second;
}
public String toString()
{
return "(" + this.first + " , " + this.second+ ")";
}
public boolean equals(Object other) {
if(other == null) {
return false;
}
if(!(other instanceof Pair)) {
return false;
}
Pair otherPair = (Pair)other;
return this.first == otherPair.first && this.second == otherPair.second;
}
}
Get Answers For Free
Most questions answered within 1 hours.