Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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);
    }
}
share|improve this question

5 Answers 5

Naming

The Java naming convention for arguments is camelCase. You should rename :

public int solution(int[] A) 

For something that could look like the following code, or use a better name that would fit your need :

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.

Formating

You're 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++)

Ps: I will not evaluate your algorithm, since this is not my force

share|improve this answer
1  
I would have gone for array –  konijn Mar 14 at 17:51

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;
}
share|improve this answer
    
Basically, the same solution as @konijn's. –  200_success Mar 14 at 18:31
    
This solution will not work when the input contains negative values... The sum of the two sides will not be increasing –  rolfl Mar 14 at 18:31
    
@rolfl Could you provide a counterexample? –  200_success Mar 14 at 18:32
    
Never mind, I misread your description vs your implementation. Your description says 'keep a running total of the left sum', but that is not what your code does, your code calculates the complete total of all values, and then subtracts things. –  rolfl Mar 14 at 18:37
    
Except that my last Java code was in 1.4, so I wrote some JavaScript ;) –  konijn Mar 14 at 18:39

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.

share|improve this answer
    
Thanks for the explanation –  Saba Mar 15 at 1:56

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;
}
share|improve this answer
    
another interpretation..thanks –  Saba Mar 15 at 1:57

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

share|improve this answer

protected by Community Aug 23 at 19:18

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.