-2

Given an array of numbers return true if there is a place to split the array so that the sum of the numbers on one side is equal to the sum of the numbers on the other side.

Here's as far as I got. Please help:

function splitSum(arr) {
    if(arr.length % 2 === 0) {
        if ()
    }
}
greybeard
  • 2,249
  • 8
  • 30
  • 66
Rory Perro
  • 441
  • 2
  • 7
  • 16
  • well, first of all, it doesn't necessarily have to be even to pass the rule u gave, take an array such as: `[ 5, 2, 3, 6, 4 ]` its not even, and when i split it after the third position, both sides add up to `10` – maraaaaaaaa Aug 22 '15 at 21:50
  • 1
    or http://stackoverflow.com/questions/28602338/split-array-to-approximately-equal-chunks?s=2|1.1904 or http://stackoverflow.com/questions/13111970/how-to-split-an-array-into-two-subsets-and-keep-sum-of-sub-values-of-array-as-eq?s=3|0.8337 or http://stackoverflow.com/questions/25967177/determine-whether-or-not-can-an-array-of-numbers-can-be-divided-into-two-arrays or http://stackoverflow.com/questions/5898104/how-to-optimally-divide-an-array-into-two-subarrays-so-that-sum-of-elements-in-b, possibly more. – beaker Aug 22 '15 at 21:53
  • Of those questions, I would suggest that http://stackoverflow.com/questions/28602338/split-array-to-approximately-equal-chunks is the closest match. Some of the others are quite different. That said, I don't think there's enough information here to tell. Rory, what part of the problem do you need help with? What have you thought about so far? – Weeble Aug 22 '15 at 22:02
  • @beaker You could have chosen a question with a correct accepted answer. The accepted answer in the other question is just plain wrong. – Juan Lopes Aug 22 '15 at 22:11
  • @beaker The suggested duplicate isn't. It's a completely different problem. – n. m. could be an AI Aug 22 '15 at 22:16
  • linear-time soln for God's sakes. how could it be. – Roam Aug 22 '15 at 22:17
  • @JuanLopes It's quite possible, and others can choose to close based on whichever duplicate they prefer and the one with the most votes will come out on top. To be honest, based on the lack of effort in the question, I didn't put in too much effort myself. My bad. – beaker Aug 22 '15 at 22:18
  • @n.m. Close vote retracted. Perhaps Weeble's suggestion of http://stackoverflow.com/questions/28602338/split-array-to-approximately-equal-chunks is a better fit. – beaker Aug 22 '15 at 22:30
  • 1
    possible duplicate of [what is the best algorithm to use for this problem](http://stackoverflow.com/questions/4609955/what-is-the-best-algorithm-to-use-for-this-problem) – Blastfurnace Aug 22 '15 at 22:49
  • 2
    Apparently people are overthinking it here. The problem does not allow for arbitrarily splitting of the elements into two sets (that would be a classic NP-complete problem). The problem simply asks for a point in the current fixed ordering. It is a kindergarten-level problem – AnT stands with Russia Aug 23 '15 at 00:16

6 Answers6

1

This can be solved in a pretty simple manner:
Just iterate over all possible positions for splitting the array, starting with an empty left array and right array is equal to the input-array and calculate the total sum of both chunks. Now simply move the first element in the array from the right to the left chunk. The total sums change in a pretty simple way: assume we remove n from the right chunk, simply substract n from the right chunk and add it the sum of the left chunk.

int equilibrium(int[] i)
    int splitBefore = 0;
    int left = 0;
    int right = sumof(i);

    for(; splitBefore < length(i) ; splitBefore++)        
        if(left == right)
            return true;

        left += i[splitBefore];
        right -= i[splitBefore];

    return left == right;
0
public boolean canBalance(int[] nums) {
  int left = 0;
  int right=0;
  for(int k=0;k<nums.length; k++) {
   right+=nums[k];
  }
  for(int i=0; i<nums.length-1; i++) {
    if(left!=right) {
      left+=nums[i];
      right-=nums[i];
    }
  }
  return left==right;
}
pioneer2019
  • 1
0

Here is commented answer hope it explains everything :)

public boolean canBalance(int[] nums) {
  int p1 = 0; // a pointer to start of array
  int p2 = nums.length-1; // a pointer to end of array
  int sum1=0;// sum1 for left side elements sum taken care by p1
  int sum2=0;// sum2 for right side elements sum taken care by p2
  for(int i=0;i<nums.length;i++){
    //run upto the length of array

    sum1+=nums[p1]; // summing left side elements
    sum2+=nums[p2];//adding right side elements

    if(sum1==sum2 && Math.abs(p1-p2) == 1){
      //if two sums become equal and the pointers differ by only one position
      //then we got the answer
      return true;
    }
    if(sum1 == sum2){
        //two sums are equal means elements are equal on both sides
        //hence move both pointers
            p1++;
            p2--;
            }
            else if(sum1 > sum2){
              // sum1 is greater then need to make sum2 bigger hence move p2
              p2--;
              sum1-= nums[p1];//removing repeated addition when p2 is changed
            }
            else{
              // sum2 is greater then need to make sum1 bigger hence move p1
              p1++;
              sum2-=nums[p2];//removing repeated addition when p1 is changed
            }

  }
  return false;


}
Varad Paralikar
  • 81
  • 1
  • 11
0
public boolean canBalance(int[] nums) {
  int leftSum = 0;
  int rightSum = 0;
  for (int i = 0; i < nums.length; i++){
        leftSum += nums[i];
        for (int j = i+1; j < nums.length; j++){
          rightSum += nums[j];
        }
        if (leftSum == rightSum)
          return true;
        rightSum = 0;
  }
  return false;
}
justNate
  • 1
  • 2
  • just adding to other's answer. the outer loop checks the left side answer, while the inner loop calculates the right side answer. the inner loop begins on the next index after the outer loop. the inner loop must be reset after a failed attempt – justNate Jul 22 '20 at 20:24
  • `the inner loop must be reset after a failed attempt` only if numbers with an index above `i` were allowed to change. – greybeard Apr 25 '21 at 06:32
0

I solved this in a different way. If we want to split the array as equal array must be divisible by 2. When you start adding the list from the left side you will reach a point the left side will be equal to half of the total.

public boolean canBalance(int[] nums) {
  int total = 0, half = 0; 
  for(int i = 0; i < nums.length; i++)
  {
    total = nums[i] + total;
  }
  if(total % 2 == 1)
  {
    return false;
  }
  for(int i = 0; i < nums.length; i++)
  {
    half = nums[i] + half;
    if(half == total / 2)
    {
      return true;
    }
  }
  return false;
}
user2960466
  • 1
0

A solution in Python:

a = [2,1,1,2,1]
for i in range(len(a)):
    a1 = a[:i+1]
    a2 = a[i+1:]
    if sum(a1) == sum(a2):
        print(a1)
        print(a2)
wuerfelfreak
  • 2,363
  • 1
  • 14
  • 29
Dataman
  • 27
  • 1
  • 6
  • 1
    Please add an assessment of the number of additions used, and compare to pre-existing answers, in particular [justNate's](https://stackoverflow.com/a/63042435/3789665). – greybeard Apr 25 '21 at 06:30