I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Balancing Arrays

07.11.2013
| 5518 views |
  • submit to reddit

It's Thursday already, so time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Balancing Arrays 

Given an array of numbers,  return the index at which the array can be balanced by all numbers on the left side add up the the sum of all numbers of the right side. For example, an array with 

[1,5,6,7,9,10] can be balanced by splitting the array at position 4.   

Catch up on all our previous puzzlers here

Comments

Safayar Ahmed replied on Thu, 2013/07/11 - 4:12am

What if there is no such index?

sun east replied on Thu, 2013/07/11 - 6:06am

In scala (return -1 if there is no index satisfied the condition):

scala> def blance(xs: Seq[Int]): Int = {
     |   xs.scanLeft(0)(_+_).indexWhere(2*_ == xs.sum)
     | }
blance: (xs: Seq[Int])Int

scala> blance(Array(1,5,6,7,9,10))
res1: Int = 4

James Sugrue replied on Thu, 2013/07/11 - 6:33am in response to: Safayar Ahmed

Good point. You can just return -1 then :)

Safayar Ahmed replied on Thu, 2013/07/11 - 8:03am

Using Java

public static int balanceIndex(int[] array) {
        long sum = 0L;
        for(int var: array) {
            sum += var;
        }
        
        if((sum%2)!=0)
            return -1;
        else {
            int index = 0;
            long left = 0L;           
            do {
                if(2*left == sum) return index;
                else if(2*left > sum) return -1;
                else {
                   left = left + array[index++];
                }
            }while(array.length > index);
            
            return -1;
        }
    }

sun east replied on Thu, 2013/07/11 - 10:43am in response to: Safayar Ahmed

Your code would not work if the array contains negative numbers.

Martin Frys replied on Thu, 2013/07/11 - 12:03pm

The beauty of the puzzle is in the one pass solution ;)
public static int balance(int[] array) {
    int left = 0;
    int right = array.length;
    long sumLeft = 0;
    long sumRight = 0;

    while (left < right) {
        if (sumLeft < sumRight) {
            sumLeft += array[left++];
        } else {
            sumRight += array[--right];
        }
    }
    return (sumLeft == sumRight) ? left : -1;
}

jusio replied on Thu, 2013/07/11 - 12:13pm

function balance(array){
  var right = array.reduce(function(a,b){
    return a + b;
  });
  var left = 0;
  for(var i = 0; i < array.length;i++) {
    var curr = array[i] 
    if(left === right){
      return i;
    }
    left += curr;
    right -= curr;
   }
  return -1;
}

Fausto Almeida replied on Thu, 2013/07/11 - 12:23pm

My version in Java... :)

public static int getBalanceIndex(int[] array) {
	int sumL = 0;		
	for (int i=0; i<array.length-1; i++) {
		sumL += array[i];
		int sumR = 0;
		for (int j=array.length-1; j>i; j--) {
			sumR += array[j];
		}
		if (sumL >= sumR) {
			return i;
		}
	}
	return -1;
}

Sam Fly replied on Thu, 2013/07/11 - 4:31pm

Another java solution

	public static int balance(int[] array) {
		Map<Integer, Integer> sumIndex = new HashMap<Integer, Integer>();
		int sum = 0;
		for (int i = 0; i < array.length; i++) {
			sum += array[i];
			sumIndex.put(sum * 2, i);
		}
		Integer result = sumIndex.get(sum);
		return result == null ? -1 : result + 1;
	}

Sean Landsman replied on Fri, 2013/07/12 - 3:17am

How about this - covers a few additional scenarios (such as unsorted, equal sized arrays etc):


public static void main(String[] args) {
    int[] array = {1, 5, 6, 7, 9, 10};
    assert findIndex(array) == 4 : "Index not what was expected";

    array = new int[]{10, 9, 7, 6, 5, 1};
    assert findIndex(array) == 2 : "Index not what was expected";

    array = new int[]{5, 3};
    assert findIndex(array) == -1 : "Index not what was expected";

    array = new int[]{10, 2, 2, 10};
    assert findIndex(array) == 2 : "Index not what was expected";

    array = new int[]{10, 1, 1, 2, 10};
    assert findIndex(array) == 3 : "Index not what was expected";

    array = new int[]{1,1};
    assert findIndex(array) == 1 : "Index not what was expected";

    array = new int[]{};
    assert findIndex(array) == -1 : "Index not what was expected";

    array = new int[]{1};
    assert findIndex(array) == -1 : "Index not what was expected";
}

private static int findIndex(int[] array) {
    Map mapLeft = new HashMap();
    Map mapRight = new HashMap();
    int sumLeft = 0;
    int sumRight = 0;
    for (int i = 0; i < array.length; i++) {
        sumLeft += array[i];
        mapLeft.put(i, sumLeft);

        int indexRight = array.length - 1 - i;
        if (indexRight >= 0) {
            sumRight += array[indexRight];
            mapRight.put(indexRight - 1, sumRight);
        }
    }

    for (int i = 0; i + 1 < array.length; i++) {
        if (mapLeft.get(i).equals(mapRight.get(i))) {
            return i + 1;
        }
    }
    return -1;
}

Frédéric Vergez replied on Fri, 2013/07/12 - 6:58am

Haskell:

let balance a = elemIndex ( quot (sum a) 2 ) $ scanl (+) 0 a

balance [1,5,6,7,9,10]
Just 4

Prabhath Kausthubha replied on Thu, 2013/07/18 - 3:44am

    private static int balance(int[] array) {
        int sum = 0;
        int index = 0;
        int lSum = 0;

        for (int i : array) {
            sum += i;
        }

        while (index < array.length) {
            lSum += array[index];
            
            if (lSum == sum / 2) {
                return index+1;
            }
            index++;
        }

        return -1;
    }

How about this ?


Star Duster replied on Thu, 2013/07/18 - 4:54pm

I fear all current solutions suffer from the implicit assumption that the numbers are only positive!

If negative input numbers were allowed (like int makes think) there might be more than one index and therefore probably more than one return code. If there would be no solution the resulting collection should be empty.

Bob Beechey replied on Thu, 2013/07/18 - 7:56pm

Python, using a list to simulate an array, has the virtue of compact simplicity. (The solution returns an incorrect answer if an earlier element matches the pivot element but I like the simplicity so have left this bug as a feature(??). It handles negative integers correctly.

 
 

def balanced_at(array):
    for each_pos in array:
        the_index = array.index(each_pos)
        if sum(array[:the_index])==sum(array[the_index:]):
            return the_index
    return -1

test_array = [1,5,6,7,8,11]
print('Balanced at',balanced_at(test_array))

Rafael Naufal replied on Sun, 2013/07/21 - 2:32pm

In Ruby:
v=[1,5,6,7,9,10];sum = v.reduce(:+);count=0;index = (0...v.size).detect { |i| count += v[i]; count * 2 == sum};index == nil ? nil : index + 1
Result: index = 4

Camilo Rivera replied on Tue, 2013/10/29 - 4:51am

Ruby solution. Returns idx such that left array goes from 0 to idx inclusive, the rest is the right array. If no solution is found the method returns null.

def balance(array)
  idx = 0
  res = array.length/2
  while res != nil && res != 0 do
    idx = idx + res
    res = balance_split(array, idx)
  end
  res == nil ? nil : idx
end

def balance_split(array, idx)
  return nil if idx == 0 || idx == array.length
  left, right = array[0...idx], array[idx..-1]
  suml = left.inject{|sum,n| sum + n}
  sumr = right.inject{|sum,n| sum + n}
  suml < sumr ? 1 : suml > sumr ? -1 : 0
end

Camilo Rivera replied on Tue, 2013/10/29 - 6:24pm in response to: Martin Frys

Nice solution Martin Frys

Marian Kamenistak replied on Mon, 2013/11/04 - 10:01am

In Java: 


public static int center(int[] array) {
  int left = 0;
  int right = array.length;
  long sumLeft = 0;
  long sumRight = 0;

  while (left < right) {
		if (sumLeft < sumRight) {
		    left++;
			sumLeft += array[left];
		} else {
		    right--;
			sumRight += array[right];
		}
	}
	return (sumLeft == sumRight) ? left : -1;
}

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.