Tape Equilibrium

Question

I picked the first test (Tape Equilibrium) from Codility here.

Question:

A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape. Any integer P, such that 0 < P < N, splits this tape into two non−empty parts:

   A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of:

 |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.For example, consider array A such that:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7 
P = 2, difference = |4 − 9| = 5 
P = 3, difference = |6 − 7| = 1 
P = 4, difference = |10 − 3| = 7 

Write a function: int solution(int A[], int N); that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.

This is how I implemented it. I got 50% with complexity N*N. How could I make it cleaner?

// you can also use imports, for example:
import java.math.*;
import java.util.*;
import java.lang.*;
class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 7
        int sizeOfArray = A.length;
        int smallest = Integer.MAX_VALUE;
        int  result = 0;
        for(int i=1;i<sizeOfArray;i++){
            int difference = Math.abs(sumOfArray(subArray(0,i,A))-
            sumOfArray(subArray(i,sizeOfArray,A)));
            //System.out.println("difference"+difference);
            result = Math.min(smallest,difference);
            smallest = result;
        }

        return result;
    }

    public int sumOfArray(int[] arr) {
        int sum=0;
        for(int i:arr) {
            sum += i;
        }

        return sum;
    }

    public int[] subArray(int begin, int end, int[] array) {
        return Arrays.copyOfRange(array, begin, end);
    }
}

Answer 1

Naming

The Java naming convention for arguments is camelCase. You should rename this argument A here:

public int solution(int[] A) 

It would be best to make it look like the following code, or use a better name that would fit your needs:

public int solution(int[] arrayA) 

I don't have anything against a variable named arr for an int [], but you're using arr and array in different methods. I would recommend to stick to one name, or try to find less generic name if they mean different things.

Formatting

Your formatting is very good in general, and you're consistent. Some times, you could use a little bit of white-space.

for(int i=1;i<sizeOfArray;i++)

You could add some spaces to clearly define the three part of the for-loop:

for(int i=1; i<sizeOfArray; i++)

I will not evaluate your algorithm, since this is not my forte.

Answer 2

You should be able to do it in \$O(n)\$ time and \$O(1)\$ space. Keep a running total of the left sum and the right sum. As you test each \$p\$, deduct a number from one side and credit it to the other.

public static int minDiff(int[] a) {
    int leftSum = 0, rightSum = 0;
    for (int ai : a) {
        leftSum += ai;
    }
    int minDiff = Integer.MAX_VALUE;
    for (int p = a.length - 1; p >= 0; p--) {
        rightSum += a[p];
        leftSum -= a[p];

        int diff = Math.abs(leftSum - rightSum);
        if (diff == 0) {
            return 0;
        } else if (diff < minDiff) {
            minDiff = diff;
        }
    }
    return minDiff;
}

Answer 3

From a once over,

you seem to call sumofArray a number of times, you should only have to call it once.

At the very beginning, you call it once for the entire array, results should be 13
Then for position 0 (value 3), you substract 3 and get 3 and 10 ( 13 - 10)
Then for position 1 (value 1). you add 1 to 3 and subtract 1 from 10 giving 4 and 9
Then for position 2 (value 2), you add 2 to 4 and substract 2 from 9 giving 6 and 7

etc. ad nauseum.

This way you access all elements twice, if I count correctly.

As I mentioned in a comment, I would rename arr -> array

I am no Java expert, but JavaScript is close enough that you should be able to follow:

var A = [3,1,2,4,3];

function sumArray( array )
{
  var sum = 0, index = array.length;
  while(index--)
    sum += array[index];
  return sum;
}

function tapeEquilibrium( array )
{
  var left = sumArray( array ),
      right = 0,
      smallest = left,
      index = array.length,
      difference;

  while( index-- )
  {
    right += array[index];
    left  -= array[index];
    difference = Math.abs( right-left );
    if( difference < smallest )
      smallest = difference;      
  }
  return smallest;
}

console.log( tapeEquilibrium( A ) );

The added advantage is that very little extra memory is required when very large arrays need to be examined.

Answer 4

The trick to this problem is in the algorithm. A solution of \$O(n)\$ complexity is available if you process the data in a 'clever' way. Consider the following algorithm:

• create a new array of the same size, call it sum
• populate the sum array with the sum of all values to the left in the original data array
• Once the sum array is fully populated, you will know what the total sum is for the array.
• this allows you to determine what the balance-point-sum is, it will be half of the total.
• you may be tempted to just binary search the sum array for the place that is half the total, but this will fail if there are negative values in the input array.
• the only solution is to scan the sums looking for half the value, with some short-circuit if there is an exact half found.

Putting it together as code, it looks like:

public static final int tapeEquilibrium(int[] data) {
    if (data.length < 3) {
        // rules indicate 0 < P < N which implies at least 3-size array
        throw new IllegalStateException("Need minimum 3-size array input");
    }
    int[] sums = new int[data.length];
    for (int i = 1; i < sums.length; i++) {
        sums[i] = sums[i - 1] + data[i - 1];
    }
    int total = sums[sums.length - 1] + data[data.length - 1];
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < sums.length; i++) {
        int diff = Math.abs((total - sums[i]) - sums[i]);
        if (diff == 0) {
            return 0;
        }
        if (diff < min) {
            min = diff;
        }
    }
    return min;
}

Answer 5

Just a minor note to add about the original code which was not mentioned earlier:

The code uses subArray only for summarizing:

int difference = Math.abs(sumOfArray(subArray(0,i,A))-
sumOfArray(subArray(i,sizeOfArray,A)));

It would be faster with the original array:

public int sumOfArray(int[] array, int begin, int end) {
    int sum = 0;
    for (int i = begin; i < end; i++) {
        sum += array[i];
    }
    return sum;
}

+1: An extra tab in the second line above the would make it clear that it's one statement:

int difference = Math.abs(sumOfArray(subArray(0,i,A))-
    sumOfArray(subArray(i,sizeOfArray,A)));

This makes the code easier to read (and maintain).