MinAbsSum.java

package codility;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 * Score 72%
 * 
 * https://codility.com/programmers/task/min_abs_sum/
 * 
 * Correct but fils performance tests because it is O(N²)
 * 
 * We need to be smarter how we run through the main loop near line 65

 */
public class MinAbsSum {

	public int solution(int[] A) {

		int N = A.length;

		if (N == 0)
			return 0;

		int s = 0;
		int result;

		/* Convert all input numbers to abs value and also 
		sum up the whole array.*/
		for (int i = 0; i < N; i++) {
			A[i] = Math.abs(A[i]);
			s += A[i];
		}

		/*Create an array to track which sums can be created 
		 * by combinations of the elements in the input array A.
		 * Elements from A can only be used once.
		 * 
		 * For example, if A = { 1, 5 }, sum =6
		 * 
		 * int[] possibleSums will be { true, true, 0, 0, 0, true, true}
		 * 
		 * indicating that a sum of 0, 1, 5 and 6 can be 
		 * made by combining zero to 2 of the elements from A.
		 * 
		 * possibleSums[0] is always one since we can always 
		 * make the sum of zero by choosing none of the elements from A.
		 */
		boolean[] possibleSums = new boolean[s + 1];

		// Initialize to zero and set possibleSums[0] = true;
		possibleSums[0] = true;
		for (int i = 1; i < possibleSums.length; i++) {
			possibleSums[i] = false;
		}

		/* For each element in A, first scan possibleSums
		 * for any flags that are already set, and for each one
		 * set possibleSums[j+num] to true (if the index is in range).
		 * For example if possbileSums[1] = true and num is 5, the 
		 * possibleSum[1+5] is also true, since we can form a sum of 6.
		 * 
		 */
		for (int i = 0; i < N; i++) {
			int num = A[i];

			//Order of initialization is important.
			for(int j=possibleSums.length-1; j>0; j--) {
				if (possibleSums[j]  && j + num < s + 1)
					possibleSums[j + num] = true;
			}
			
			//Order is important. This must not be moved above the j-loop.
			possibleSums[num]=true;
		}
		
		result = s;
		
		// p is the largest sum that we can make that is < s/2
		for(int p=0; p*2 <= s; p++) {
			if( possibleSums[p] ) {
				int q = s -p;
				result = Math.min(result,  q-p);
			}
		}
		

		return Math.abs(result);
	}

	class TestCase {
		int expectedResult;
		int[] input;
		
		public TestCase(int expectedResult, int[] input) {
			super();
			this.expectedResult = expectedResult;
			this.input = input;
		}
		
		
	}
	
	public static void main(String args[]) {
		MinAbsSum instance = new MinAbsSum();

		List<TestCase> testCases = new ArrayList<TestCase>();
		
		testCases.add(instance.new TestCase(4,new int[] { 1, 5}));
		testCases.add(instance.new TestCase(0,new int[] { 1, 5, 2, -2 }));
		testCases.add(instance.new TestCase(1,new int[] { 2 ,2, 1 }));
		testCases.add(instance.new TestCase(91,  new int[] {-100,3,2,4}));
	

		for(TestCase testCase : testCases) {
			int result = instance.solution(testCase.input);
			if(testCase.expectedResult == result)
				System.out.println("pass: "+Arrays.toString(testCase.input)+"->"+result);
			else
				System.out.println("fail: "+Arrays.toString(testCase.input)+"->"+result+"\texpected "+testCase.expectedResult);
		}
	}
	
	
}