## Find K Complementary numbers from array Java implementation

### 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.

``````
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
*/
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

## Find longest palindrom from sequence of characters

### Given the string, find the longest palindrom you can form from it

``````
/**
* @author gullele.com
*/
public class LongestPalindrom {
public static void main(String[] args) {
LongestPalindrom longest = new LongestPalindrom();
System.out.println(longest.longest("zzbmbmbdmm"));
}

public String longest(String string) {
if (string.length() == 0 || string == null) {
return "";
}

StringBuffer palindrom = new StringBuffer();
Map charBag = new HashMap();
for (Character c : string.toCharArray()) {
int totalChar = charBag.get(c) != null ? charBag.get(c) : 0;
if ((totalChar + 1) % 2 == 0) {
palindrom.append(c);
palindrom = palindrom.insert(0, c);
charBag.remove(c);
continue;
}
charBag.put(c, ++totalChar);
}

if (charBag.size() > 0) {
Iterator it = charBag.entrySet().iterator();
Map.Entry pair = (Map.Entry)it.next();
String c = pair.getKey().toString();
palindrom.insert(palindrom.length()/2, c);
}
return palindrom.toString();
}
}

``````

## Check if there are three numbers a, b, c giving a total T from array A

I got this question while helping a friend on the course work. It is relatively simple question. But the way how it is approached can make a difference on efficiency.

The question is, given an array of numbers, you are to find if there are three numbers that would total the given number T.

If done in a very naive way, it can soar to o(n^3) like having three loops and checking the sum inside the third loop.. well.. this is a no no..

I have approached it in a log n ( for sorting) and n for (searching) approach..

``````
package algorithm;

import java.util.Arrays;

/**
* Given an array of integers, find if there are three numbers that would sum up to the
* number T
*
* @author http://gullele.com
*
*/
public static void main(String[] args) {
int[] test = new int[]{1,3,4,5,10,12, 18};

int[] response = summt.findThreeNumbers(test, 29);

if (response.length > 1) {
for(int num : response) {
System.out.println(num);
}
} else {
System.out.println(":( Couldn't find those three gems");
}

}

public int[] findThreeNumbers(int[] nums, int t) {

int[] indexes = new int[1];
if (nums.length == 0 || nums.length <= 2) {
return indexes;
}

//for primitive this would be quick sort so we have nlogn
Arrays.sort(nums);

int minIndex =0;
int maxIndex = nums.length-1;
int current = 1;
while (minIndex != maxIndex) {
if (nums[minIndex] + nums[maxIndex] + nums[current] == t) {
int[] summingNumbers = new int[3];
summingNumbers[0] = nums[minIndex];
summingNumbers[1] = nums[current];
summingNumbers[2] = nums[maxIndex];
return summingNumbers;
}

int lookingFor = t-(nums[minIndex] + nums[maxIndex]);
//if the number being sought is beyond the max, then jack up the min index
if (lookingFor >= nums[maxIndex]) {
minIndex++;
current = minIndex + 1;
} else if (nums[minIndex] + nums[maxIndex] + nums[current] < t) {
current++;
} else {
maxIndex--;
current = minIndex + 1;
}

}

return indexes;
}
}

```
```