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

08.22.2012
| 5043 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. 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!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Balancing Arrays

In today's challenge, given an array of values, write a method that returns the index of the point in the array where the sum of numbers on one side is equal to the sum of the numbers on the other side. The method returns -1 otherwise.

So for the array {1,1,1,1} you could return index 1 as we break the array after the second element to balance it.

Catch up on all our previous puzzlers here.

Comments

Andreas Kaubisch replied on Thu, 2012/08/23 - 2:12am

one Java solution. Hope its correct ;)

import java.util.Arrays;

public class Balancer {

    public static int splitArray(int[] iArray) {
        int sum = 0;
        for(int i : iArray) {
            sum += i;
        }
      
        int idx = -1;        
        if(sum % 2 == 0) {
            for(int i=0, maxValue = sum/2,maxIdx = iArray.length -1; i <= maxIdx; i++) {
                maxValue -= iArray[i];
                if(maxValue == 0 && i != maxIdx) {
                    idx = i;
                    break;
                }
            }
        }
        return idx;
    }
    
    public static void main(String[] args) {
        int[] arr = new int[] {1,2,3,3,2,1};

        int idx = Balancer.splitArray(arr);
        if(idx != -1) {
            int[]  left = new int[idx+1];
            int[] right = new int[arr.length-left.length];
            System.arraycopy(arr, 0, left, 0,left.length);
            System.arraycopy(arr, idx+1, right, 0, right.length);
            System.out.println("original:"+Arrays.toString(arr) +" left:"+ Arrays.toString(left) + " right:" + Arrays.toString(right));
        }
    }

Vijay Nathani replied on Thu, 2012/08/23 - 3:41am

Groovy solution
def splitOnSum(numbers) {
	def (start,last,sumOfStart,sumOfLast) = [0, numbers.size()-1,numbers.first(), numbers.last()]
	while ( last - start > 1) 
		(sumOfStart < sumOfLast)?(sumOfStart += numbers[++start]): 		(sumOfLast += numbers[--last])
	(sumOfStart == sumOfLast)?start:-1
}
println splitOnSum([1,1,1,1]) //prints 1
println splitOnSum([1,2,3,4]) //prints -1

Neeraj Khapre replied on Thu, 2012/08/23 - 7:41am

import java.util.Arrays;

public class ArrayBalancer {
	
	public static int getIndex(int[] arr, int sumTotal) {
		int halfOfSum = sumTotal / 2;
		int sum = 0, ind = -1;

		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
			if (sum == halfOfSum) {
				ind = i;
				break;
			}
		}
		return ind;
	}

	public static void balanceArray(int[] arrTest) {
		int arrSum = 0;

		for (int element : arrTest)
			arrSum += element;

		if (arrSum % 2 == 0) {
			int index = getIndex(arrTest, arrSum);
			if (index != -1) {
				int[] part1 = new int[index + 1];
				int[] part2 = new int[arrTest.length - part1.length];

				System.arraycopy(arrTest, 0, part1, 0, part1.length);
				System.arraycopy(arrTest, part1.length, part2, 0, part2.length);

				System.out.println("Original Array is " + Arrays.toString(arrTest));
				System.out.println("Part 1 is " + Arrays.toString(part1));
				System.out.println("Part 2 is " + Arrays.toString(part2));
			} else {
				System.out.println("Un-Balanced array " + index);
			}
		}else {
			System.out.println("Un-Balanced array");
		}
	}

	public static void main(String[] args) {
		int[] testArray1 = { 2, 2, 1, 3, 2, 2, 4, 3, 5 };
		int[] testArray2 = { 2, 2, 1, 3, 2, 2, 4, 3, 5, 2 };

		System.out.println("First Array");
		ArrayBalancer.balanceArray(testArray1);
		System.out.println("\n\nSecond Array");
		ArrayBalancer.balanceArray(testArray2);
	}
}

Andreas Kaubisch replied on Thu, 2012/08/23 - 8:11am in response to: Neeraj Khapre

Your function fails when you take an array like {-1, -2, -3, 1, 2, 3}.

Daniel Comsa replied on Thu, 2012/08/23 - 8:49am

    public int balanceArray(int[] array) {
        if (array == null || array.length < 2) {
            return -1;
        }

        int start = 0;
        int end = array.length - 1;
        long sumStart = array[start], sumEnd = array[end];

        while (start + 1 < end) {
            if (sumStart < sumEnd) {
                sumStart += array[++start];
            } else {
                sumEnd += array[--end];
            }
        }

        return sumStart == sumEnd ? start : -1;
    }

Artun Ozsemerciyan replied on Thu, 2012/08/23 - 9:16am

	public int findIndex(int[] array) {		
		
		for (int i=0; i<array.length; i++) {
			int leftTotal = 0;
			for (int j=0; j<=i; j++)
				leftTotal += array[j];
			
			int rightTotal = 0;
			for (int k=i+1; k<array.length; k++)
				rightTotal += array[k];			
			
			if (leftTotal == rightTotal)
				return i;
		}
		
		return -1;
	}

Peter Jodeleit replied on Thu, 2012/08/23 - 5:32pm

Plain old Java, iterative:

    public int check(final int... array) {
        int a = 0;
        int b = array.length - 1;
        if (b <= 0) return -1;
        int sumA = 0;
        int sumB = 0;
        while (a < b) {
            if (sumA <= sumB) {
                sumA += array[a];
                a++;
            }
            if (sumA >= sumB) {
                sumB += array[b];
                b--;
            }
        }
        if (a == b) {
            // tie break
            if (sumA == sumB + array[b]) return a - 1;
            if (sumA + array[a] == sumB) return a;
        } else if (sumA == sumB) {
            return a - 1;
        }
        return -1;

 

sun east replied on Thu, 2012/08/23 - 8:23pm

Scala :

def balanceIndex(xs: Seq[Int]): Int = {
  val sum = xs.sum
  xs.scanLeft(0){ _+_ }.tail.indexWhere{ 2*_ == sum }
} 

 Some usecase:

 

  • scala> balanceIndex(Array(1,1,1,1))
  • res0: Int = 1
  • scala> balanceIndex(Seq(1,2,3,4))
  • res1: Int = -1
  • scala> balanceIndex(5::4::3::2::1::1::2::3::4::5::Nil)
  • res2: Int = 4 

 

sun east replied on Thu, 2012/08/23 - 8:42pm

Matlab(Note that the array index starting with 1 instead of 0):

 

 >> balanceIndex = @(v) find(2*cumsum(v) == sum(v)); 

 

 

  • >> balanceIndex([1 1 1 1])
  • ans =
  •      2
  • >> balanceIndex([1 2 3 4])
  • ans =
  •    Empty matrix: 1-by-0
  • >> balanceIndex([1 2 3 4 4 3 2 1])
  • ans =
  •      4

 

Jorge Bescos replied on Fri, 2012/08/24 - 5:06am

public static int getMiddleSumIndex(final int[] array){
		final int NOT_FOUND=-1;
		int leftIdx=0;
		int rightIdx=array.length-1;
		int sumLeft=array[leftIdx];
		int sumRight=array[rightIdx];
		while(leftIdx<rightIdx){
			if(sumLeft<=sumRight)
				sumLeft+=array[++leftIdx];
			if(sumRight<sumLeft)
				sumRight+=array[--rightIdx];
			if(sumRight==sumLeft && (leftIdx+1)==rightIdx)
				return leftIdx;
		}
		return NOT_FOUND;
	}

Gonzalez Roberto replied on Fri, 2012/08/24 - 5:00am

Java:

 

public static int findIndex(int[] array) {
        int iIndex = -1;
        int jIndex = array.length;
        long sum = 0;
        while(jIndex - iIndex > 1 && array.length != 1){
            long auxSum = 0;
            if (sum <= 0)
                auxSum = array[++iIndex];
            
            if (sum >= 0)
                sum -= array[--jIndex];

            sum += auxSum;
        }
        return sum == 0 ? iIndex : -1;
    }

 

Niels De Feijter replied on Fri, 2012/08/24 - 4:46am

The code:

    public static int balanceArray(int[] array) {
        int left = 0, right = 0;
        for (int i = 0; i < array.length; i++) 
            right += array[i];
        for (int i = 0; i < array.length -1; i++) 
            if ((left += array[i]) == (right -= array[i])) 
                return i;
        return -1;
    }

And a little test driver:

    public static void main(String[] args) {
        assert -1 == balanceArray(new int[] {});
        assert -1 == balanceArray(new int[] {1});
        assert -1 == balanceArray(new int[] {-1, 1});
        assert  0 == balanceArray(new int[] {1, 1});
        assert  1 == balanceArray(new int[] {1, 1, 1, 1});
        assert  1 == balanceArray(new int[] {1, 4, 2, 3});
        assert -1 == balanceArray(new int[] {-1, -2, -3, 1, 2, 3});
        assert  2 == balanceArray(new int[] {-1, -2, -3, -1, -2, -3});
        assert  2 == balanceArray(new int[] {1, 2, 3, 1, 2, 3});
        assert  0 == balanceArray(new int[] {5, 1, 1, 1, 1, 1});
        assert  1 == balanceArray(new int[] {5, -1, 1, 1, 1, 1});
    }

Peter Jodeleit replied on Fri, 2012/08/24 - 5:05am in response to: Gonzalez Roberto

@ Gonzalez Roberto:
Nice solution (evolution?). But misses the corner case "array with one element".

Gonzalez Roberto replied on Fri, 2012/08/24 - 5:18am in response to: Peter Jodeleit

It's true :( Thanks Peter

Николай Русев replied on Fri, 2012/08/24 - 7:41am

System.out.println(findBalanced(array));
	private static int findBalanced(int[] array){
		int balanced = -1;
		for(int i = 0;i<array.length;i++){
			int right[] = Arrays.copyOfRange(array, i, array.length);
			int left[] = Arrays.copyOfRange(array, 0, i);
			if( sumArray(left) == sumArray(right) )
				balanced =  i;
		}
		return balanced;
	}
	private static int sumArray(int[] array){
		int sum = 0;
		for(int i : array){
			sum+=i;
		}
		return sum;
	}

Lari Tuomisto replied on Sat, 2012/08/25 - 3:31pm

C#
public static int ElementAtMiddle(this IEnumerable<int> inputArray)
{
    var array = inputArray.ToArray();
    var midpoint = array.Sum() / 2;

    var elementNumber = 0;
    var runningSum = 0;
    while (runningSum < midpoint)
    {
        runningSum += array[elementNumber];
        ++elementNumber;
    }

    if (runningSum != midpoint)
    {
        return -1;
    }

    return elementNumber;
}

Joe Colburn replied on Thu, 2012/09/13 - 10:04pm

The following returns 1 | -1 | 1 | -1 | 2 | -1 |

 

function splitBalance($array) {
    if (count($array) % 2 == 1) {
        return -1;
    }
    for ($i=0; $i<count($array); $i++) { 
        if (array_sum(array_slice($array, 0, $i+1)) == array_sum(array_slice($array, $i+1))) {
            return $i;
        }
        if ((array_sum(array_slice($array, 0, $i+1)) != array_sum(array_slice($array, $i+1))) && (($i+1) == count($array))) {
            return -1;
        }
    }
}

$arrset = array(
    array(1,1,1,1),
    array(1,2,3,4),
    array(4,1,3,2),
    array(1,1,1,1,1),
    array(4,1,6,3,6,2),
    array(4,1,2,3,6,2)
);

foreach ($arrset as $key => $value) {
    echo splitBalance($value)." | ";
} 

 

Lari Tuomisto replied on Fri, 2012/09/14 - 10:08am in response to: Joe Colburn

Joe Colburn:  Good stuff Joe, however I don't think it is valid to discard an array if the count of its elements is an odd number. The sum of the elements can still be balanced. Consider for example an array like (1,2,3) Odd number of elements, but it can be balanced.

Secondly, might be worth thinking about not having array_sum being called twice for one for loop. That very likely causes the array to be traversed twice per for loop, which means a triple for loop and a complexity of O(n^3). I think it is completely possible (haven't tried it or read about it) to traverse the array only once to get the data you need to balance it. Or you could just store the result of the left sum and right sum into a variable in the start of the for loop to avoid calling it twice. (Your if-statements have duplicate code.) 

I'm not a master in PHP, but I'm going on gut feeling and general knowledge about typical implementations. Maybe something to think about anyway :)

Rômero De Sousa... replied on Wed, 2013/06/26 - 12:54am

In Clojure:
(def seqMiddleIdx (fn [sq] (loop [rst (rest sq) sq (conj '() (first sq)) index 0] (if (empty? rst) -1 (if (= (reduce + sq) (reduce + rst)) index (recur (rest rst) (conj sq (first rst)) (inc index)))))))

Murali Chevuri replied on Thu, 2013/07/11 - 2:34pm

static int getBalancedIndex(int []a) {
		int i=0;
		int j = a.length-1;
		int ss=a[i],es=a[j];
		while(i < j) {
			if(ss==es && (j-i)==1) {
				return i;
			} else if(ss > es) {
				es += a[--j];
			} else
				ss += a[++i];
			
		}
		return -1;
	}

Comment viewing options

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