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();
}
}

``````

Maven error Annotations are not supported in -source 1.3

The Error

Are you using annotations in your project?

If so, you will get this error if you try to do `mvn compile` or `mvn install`.

You may have also seen this if you are building your project on eclipse as well.

The solution

The default maven relies on JDK 1.3 for its building the project and you might be using a JDK above 1.3. Also, JDK 1.3 does not implement annotations.

The solution is to tell the maven the current non-1.3 JDK you are using on you `pom.xml` file.

``````
<project>
.
.

<build>
<plugins>
<plugin>
<artifactId>maven-compiler-plugin</artifactId>
<version>2.3.2</version>
<configuration>
<source>1.8</source>
<target>1.8</target>
</configuration>
</plugin>
</plugins>
</build>
</project>

``````

For the source and target you will provide your current JDK you are using.

Running maven project in eclipse step by step

If you have java web project that is maven based, and you want to run the project in eclipse here are the steps.

Mind you this is for the project which is already a maven project, say you did it through terminal or you got it from other repository and you want to run it locally through eclipse.

Assumed -> you have setup the webserver like tomcat on eclipse.

1. Go to Eclipse Run->Run Configuration

2. Double click on M2 Maven Build

3. On the base directory: insert `\${project_loc}`

4. On the goals: insert `tomcat:run` and the select and apply

5. Right click on the project and select configure->Convert to Maven Project

configure build path

6. Again right click on the project and select Maven->Update Project

7. For further pulling the dependencies from maven to eclipse, right click on it->properties->Deployment Assembly

8 Click on Add button and select Java build path entries and select Maven Dependencies

9. Now, your dependencies should be pulled all is ready for testing. Go to project menu and click on build project. This will be inactive if Build Automatically is selected.

10. Then to test, right click on one of your servlet and select run as and click on the server option. If all went good, you should be able to see the output from your servlet on the browser.

The above simple steps would allow you to convert the Java web project into maven project in eclipse.

Importing packages to eclipse added by maven to java web project

If eclipse is having a hard time acknowledging the packages you got through maven, here are the step by step fix for it..

1. Go to your projects root, where the `pom.xml` resides

2. issue `mvn eclipse:clean`

3. issue `mvn eclipse:eclipse`

4. this could be optional, on eclipse go to the project, right click on it and select build project

eclipse j2ee error There are No resources that can be added or removed from the server

Eclipse showing There are No resources that can be added or removed from the server when adding project

If you are trying to test the java web application (j2ee) on your local machine with built in eclipse support and getting error, then it is related to project facet.

Here is how you can solve the error There are No resources that can be added or removed from the server coming from eclipse

1. right click on your web project in eclispe

2. Select properties

3. Select Project facets

4. Select Dynamic Web Module

5. Click on apply and then click on OK

This will solve the problem.

testing k complementary pairs algorithm with junit

This is the test class for the java solution of the k-complementary problem listed here

``````
package algorithm;

import static org.junit.Assert.assertArrayEquals;

import org.junit.Before;
import org.junit.Test;

/**
* Testing KComplementary algorithm
*
* @author Kaleb Woldearegay
*
*/
public class KComplementaryTest {

private KComplementary kComplementary;

@Before
public void initiate() {
this.kComplementary = new KComplementary();
}

@Test
public void test1() {
Integer[][] expectedResult = new Integer[][]{{1,9},{5,5},{9,1}};
int[] test = new int[]{1,5,9};

assertArrayEquals(this.kComplementary.getKComplementaryPairs(10,  test), expectedResult);
}

@Test
public void test2() {
Integer[][] expectedResult = new Integer[][]{{5,7},{7,5}};
int[] test = new int[]{3,5,7};

assertArrayEquals(this.kComplementary.getKComplementaryPairs(12,  test), expectedResult);
}

@Test
public void test3() {
Integer[][] expectedResult = new Integer[][]{{-1,1},{0,0},{1,-1}};
int[] test = new int[]{5,-1,0,-2,3, 1};

assertArrayEquals(this.kComplementary.getKComplementaryPairs(0,  test), expectedResult);
}

}
``````

See more algorithm solutions by clicking Here

Find K complementary pairs from the given array

So the problem is, given an array of numbers, you are going to find the pairs whose sum is K.

Say, if you are given `7, 1, 5, 6, 9, 3, 11, -1` and K = 10 then the pairs would be

=> 1 and 9
=> 3 and 7
=> 11 and -1

Here is the O(n) solution for the K complementary problem in java

It turns out, this is not a pure O(n) solution. Can you spot why?

``````
package algorithm;

import java.util.HashMap;
//import java.util.List;
import java.util.Map;

/**
* Algorithm to find the pairs making the K complementary in O(n) complexity
*
* @author http://gullele.com
* @see KComplementaryTest.java - a JUnit test for this class
*/
public class KComplementary {

private Map pairs;

public static void main(String[] args) {
KComplementary kcomp = new KComplementary();
int[] numbers = new int[]{7, 1, 5, 6, 9, 3, 11, -1};
Integer[][] pairs = kcomp.getKComplementaryPairs(10, numbers);

for (Integer[] thePairs : pairs) {
System.out.println(" Pairs are "+thePairs[0] + " and " + thePairs[1]);
}
}

public KComplementary() {
this.pairs = new HashMap();
}

/**
* 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). 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 Integer[][] getKComplementaryPairs(int sum, int[] listOfIntegers) {

/*
* I could have used the ArrayList assuming the number of pairs we are getting
* is not known, but giving it a little bit of thought, the number of pairs
* is known in advance, at least the maximum we can get is known.
* By not using the Array list, the algorithm would run O(n) rather than
* O(n**2) since ArrayList.add would would be O(n) by itself
*/
//List complementaryPairs = new ArrayList();
Integer[][] complementaryPairs = new Integer[listOfIntegers.length][2];
//First fill up the pairs with the complementary numbers
for (int number : listOfIntegers) { //O(n) complexity
this.pairs.put(number, sum-number);
}

//then filter out the pairs that don't have corresponding complementary number
int index = 0;
for (int number : listOfIntegers) { //O(n) complexity
int complementary = sum - number;
//check if this key exists in the pairs
if ( this.pairs.containsKey(complementary) ) {
//Had I used array List this would have been used
//Integer[] comps = {number, complementary};
complementaryPairs[index][0] = number;
complementaryPairs[index][1] = complementary;
index ++;
}
}
//System.out.println(index);
//Now trim the array since we know the exact record
Integer[][] trimmed = new Integer[index][2];

index = 0;
for (Integer[] item : complementaryPairs) { //O(n) complexity
if (item[0] != null) {
trimmed[index][0] = item[0];
trimmed[index][1] = item[1];
}
index++;
}

//Total complexity O(n)+O(n)+O(n) ==> O(n)

//had I used arrayList this would have been used
//return complementaryPairs.toArray(new Integer[0][0]);
return trimmed;
}
}

```
```

The above solution runs and would do the job without a problem. But it is not linear solution as it claims to be.

I have got another solution that would explain why and comes up with a solution for it. Check it out here

You can see the jUnit for this class also at here

Using mvn for creating and running a boilerplate minimal java application

It is almost a must to use mvn or any other build tool when dealing with java.

With mvn you can start a minimal simple all included java application and you run that too.. Just follow this. I will assume you are on linux or mac environment for this and also I am assuming you already have maven installed
Create a new folder and say mavenrocks

```mkdir mavenrocks
```

```mvn archetype:generate
```

What it does is, it will use a plugin to create a boilerplate application that holds basic src files along with standard directory structure.
if you do the listing on the created folder you will see:

```.
./pom.xml
./src
./src/main
./src/main/java
./src/main/java/com
./src/main/java/com/gullele
./src/main/java/com/gullele/App.java
./src/test
./src/test/java
./src/test/java/com
./src/test/java/com/gullele
./src/test/java/com/gullele/AppTest.java
./target
./target/classes
./target/classes/com
./target/classes/com/gullele
./target/classes/com/gullele/App.class
./target/maven-status
./target/maven-status/maven-compiler-plugin
./target/maven-status/maven-compiler-plugin/compile
./target/maven-status/maven-compiler-plugin/compile/default-compile
./target/maven-status/maven-compiler-plugin/compile/default-compile/createdFiles.lst
./target/maven-status/maven-compiler-plugin/compile/default-compile/inputFiles.lst
```

and to run it

```mvn execute:java -Dexec.mainClass="com.gullele.App"
```

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;
}
}

```
```