Find K complementary numbers from the given array
This is another approach to the problem that I have done it here. On that post, a good deal of visitors pointed out that it is actually o(n*n) not o(n) as I claimed.
Yes, the naive usage of Hashmap for holding the numbers has soared the performance and I have changed the approach as follows.
To remind the k complementary problem and its solution, you are given array of numbers and a number k of which you are going to find numbers that give k complementary. The following is an example of it.
The problem is, given numbers like 7, 1, 5, 6, 9, 3, 11, -1
and given number 10, write a script that would print numbers that would add to 10. In the example, it would be like
7 and 3, 1 and 9, -1 and 11.
Thanks Reda and mtrad for your correction.
package algorithm;
import java.util.ArrayList;
import java.util.List;
/**
* Algorithm to find the pairs making the K complementary in O(n) complexity
*
* @author http://gullele.com
*/
public class KComplementary2 {
public static void main(String[] args) {
KComplementary2 kcomp = new KComplementary2();
int[] numbers = new int[]{7, 1, 5, 6, 9, 3, 11, -1};
for (Integer number : kcomp.getKComplementaryPairs(10, numbers)) {
System.out.println(" Pairs are "+ number + " and " + (10-number));
}
}
public KComplementary2() {}
/**
* An algorithm to find the pair from the given array that would sum up the given K
*
* @note - the algorithm would be done in o(n)+o(nlogn). First it will run through the whole
* numbers and creates a temporary list of pairs in HashMap with
* (value, sum-value).
* @param sum
* @param listOfIntegers
* @return
*/
public List getKComplementaryPairs(int sum, int[] listOfIntegers) {
/*
* The algorithm works using front and last pointers on ascendingly sorted array. The front would be
* instantiated with 0 and last with length-1; if the arr[front]+arr[last] == sum, then pick
* the numbers and add them to the pair array.
* if their sum is greater than sum, it means time to check the second higher number that is lower
* than the current highest number. And the reverse would hold true if the sum is less than the sum
* time to move to the next higher number from the lower side.
*/
if (listOfIntegers == null || listOfIntegers.length == 0) {
return null;
}
//quick sort the array
quickSort(0, listOfIntegers.length-1, listOfIntegers);
int[] sortedArray = listOfIntegers;
//holder for the complementary pairs
List pairs = new ArrayList();
int frontPointer = 0;
int lastPointer = sortedArray.length-1;
while (frontPointer < lastPointer) {
int currentSum = sortedArray[frontPointer] + sortedArray[lastPointer];
if (currentSum == sum) {
/*
* Since sum is found, increment front and decrement last pointer
* Only one number is required to be hold, the other can be found
* from sum-number since complementary
*/
pairs.add(sortedArray[frontPointer]);//adding is o(1)
frontPointer++;
lastPointer--;
} else if (currentSum > sum) {
lastPointer--;
} else {
frontPointer++;
}
}
return pairs;
}
/**
* sort the numbers. I have used quick sort here. QuickSort is nlogn in average case
* well, in worst case it still would be n**2 though :(
* @param numbers
* @return sorted array numbers.
*/
public void quickSort(int lowerIndex, int higherIndex, int[] numbers) {
/*
* Recursively inarray sort. Start from arbitrary value to compare from and recursively sort its
* left and right.
*/
int pivot = lowerIndex+(higherIndex-lowerIndex)/2;
int lower = lowerIndex;
int higher = higherIndex;
while (lower < higher) {
while (numbers[lower] < numbers[pivot]) {
lower++;
}
while (numbers[higher] > numbers[pivot]) {
higher--;
}
//swap those needed to be on the left on those on the right.
if (lower <= higher) {
int temp = numbers[lower];
numbers[lower] = numbers[higher];
numbers[higher] = temp;
lower++;
higher--;
}
}
if (lowerIndex < higher) {
quickSort(lowerIndex, higher, numbers);
}
if (lower < higherIndex) {
quickSort(lower, higherIndex, numbers);
}
}
}
Love algorithms? See how you would solve the following
Can you find the three numbers that would sum to T from given array?
From a file of billion numbers, find missing numbers with limited memory
Limit BigDecimal to n decimal places
spring error ClassNotFoundException org.springframework.web.context.ContextLoaderList
The superclass “javax.servlet.http.HttpServlet” was not found on the Java Build Path
String Ordered Permutation Algorithm Problem
setting JAVA_HOME on mac osx