Given an array of numbers (assume the array has three or more values, and they are indeed numbers), return an index, if one exists, where the sums of the elements on either side of that index are equal. eg. [2, 3, 4, 4, 1] given the function this array should return index 2 (element with value 4) because the sums on either side are equal (2 + 3 = 4 + 1). 9 Answers This is trivially solved using brute force in O(n^2), but is fairly easily reduced to O(n) using two pointers pointing to the elements on either side of the current "middle element" and sum counters that keep track of the sums. You move the "middle element" through the array (skipping the first and last element) and keep track of the sums just by subtracting the element on the right and adding the element on the left. Don't forget to the get the full right sum with a loop if starting on the left of the array before iterating. int arrayTestIterative(int arr[], int len){ int rval = 0, lval = arr[0]; for (int i = 2; i <=len; i++) //since we are starting with element 1, we are concerned with rval += arr[i]; // summing elements 2 and beyond for (int k = 1;k<len;k++){ if (rval == lval) //check success conditions return k; else //update values { rval -= arr[k+1]; lval += arr[k]; } }//endfor return -1; }; int main(int argc, const char * argv[]) { int array[] = {2,3,4,4,1}; std::cout << arrayTestIterative(array , sizeof(array)/sizeof(int)-1); } Just for kicks I did a recursive version int arrayTestHelper(int arr[], int len, int cur, int lval, int rval){ if (cur == len) //if you reach the last value return with a non index# return -1; if (rval == lval) // you found the index of the sum balanced middle. return cur; else return (arrayTestHelper(arr, len, cur+1, lval + arr[cur], rval - arr[cur + 1])); }; int arrayTest(int arr[], int len) { int sum = 0; for (int i = 1; i <=len; i++) //loop to get the sum excluding the first element sum += arr[i]; return arrayTestHelper(arr, len, 1,arr[0],sum - arr[1]); }; Java Answer: import java.util.Arrays; public class BalancedSumIndex { public static int findPivotIndex(int[] inputArray) { int leftPointer = 0, leftSum = 0, rightSum = 0; int rightPointer = inputArray.length - 1; while (rightPointer != leftPointer) { if (leftSum >= rightSum) { rightSum += inputArray[rightPointer]; //System.out.println("right sum is " + rightSum); rightPointer--; } else { leftSum += inputArray[leftPointer]; //System.out.println("left sum is " + leftSum); leftPointer++; } } if (leftSum == rightSum) { return leftPointer; } return -1; } public static void main(String[] args) { int inputArray[] = new int[]{2, 3, 4, 4, 1}; System.out.println("inputArray: " + Arrays.toString(inputArray)); int pivot = findPivotIndex(inputArray); System.out.println("Pivot index is: " + pivot); inputArray = new int[]{0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 4, 1, 1, 0, 2, 9, 3, 8, 4, 7, 5, 6, 0, 0, 0, 0, 0}; System.out.println("inputArray: " + Arrays.toString(inputArray)); pivot = findPivotIndex(inputArray); System.out.println("Pivot index is: " + pivot); } } Show More Responses This is way overdone as I could just use the innards of these methods, but here is a javascript solution you can just copy and paste into the browser js console. Using Patrick's int array from above. ---------------------------------------------------------------------------- var arr = [0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 4, 1, 1, 0, 2, 9, 3, 8, 4, 7, 5, 6, 0, 0, 0, 0, 0]; ArrayCheck = function(arr){ this.thisArr = arr; } ArrayCheck.prototype.getSumBefore = function(idx) { if(idx-2 > -1){ return this.thisArr[idx-1] + this.thisArr[idx-2]; } else { return NaN; } }; ArrayCheck.prototype.getSumAfter = function(idx){ if(idx+2 < this.thisArr.length){ return this.thisArr[idx+1] + this.thisArr[idx+2]; } else { return NaN; } } ArrayCheck.prototype.getIsEqual = function(idx){ var afterSum = this.getSumAfter(idx); var beforeSum = this.getSumBefore(idx); console.log(" value: " + this.thisArr[idx]); console.log(" afterSum: " + afterSum); console.log("beforeSum: " + beforeSum); if(this.thisArr[idx] === afterSum && this.thisArr[idx] === beforeSum){ return true; } else { return false; } } ArrayCheck.prototype.findNumber = function(){ for(i=0;i<this.thisArr.length;i++){ if(this.getIsEqual(i)){ console.log("Index: " + i + " is a winner!"); } else{ console.log("Index: " + i + " is a loser.") } console.log("It's value is " + this.thisArr[i]); console.log("-------------------------"); } } Python Code: def arrayiter(array): for i,_ in enumerate(array): if sum(array[:i]) == sum(array[i+1:]): return i return -1 print arrayiter([2, 3, 4, 4, 1]) print arrayiter([0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 2, 3, 4, 4, 1, 1, 0, 2, 9, 3, 8, 4, 7, 5, 6, 0, 0, 0, 0, 0]) Output: >>> 2 12 >>> let values:[Int] = [3,1,2,1,3,4,4,1,2,1,1,1] func firstSplitIndex(list:[Int]) -> Int? { var sum:Int = 0 for value in list { sum += value } var leftSum = 0 var rightSum = 0 for i in 0..<countElements(list) { rightSum = sum - leftSum - list[i] if rightSum == leftSum { return i } leftSum += list[i] } return nil } println(firstSplitIndex(values)) for(i = 0 ; i<n; i++) { sum+=a[i]; } for(i=1; i<n-1; i++) { sum1+=a[i-1]; sum2 = sum - a[i] - sum1; if(sum1 == sum2) return i; } for(i = 0 ; i<n; i++) { sum+=a[i]; } for(i=1; i<n-1; i++) { sum1+=a[i-1]; sum2 = sum - a[i] - sum1; if(sum1 == sum2) return i; } for(i = 0 ; i<n; i++){sum+=a[i]; } for(i=1; i<n-1; i++) { sum1+=a[i-1]; sum2 = sum - a[i] - sum1; if(sum1 == sum2) return i;} |