Counting Balanced numbers in a given array I am trying a code challenge. Here is the problem description:

When an element is deleted from an array, the higher-indexed elements shift down one index to
fill the gap. A &quot;balancing element&quot; is defined as an element that, when deleted from the array,
results in the sum of the even-indexed elements being equal to the sum of the odd-indexed
elements. Determine how many balancing elements a given array contains.


Example
n=5 where n is the size, arr = [5, 5, 2, 5, 8]


When the first or second 5 is deleted, the array becomes [5, 2, 5, 8]. The
sumeven = 5 + 5 = 10
and sumodd = 2 + 8 = 10. No other elements of the original array have that
property.


There are 2 balancing elements that is arr[0] and arr[1].

And here is my solution:
public class Challenge {
  public static void main(String[] args) {
    countBalancingElements(new int[] {1, 1, 1});
  }
  static int countBalancingElements(int[] arr) {
    int count = 0;
    for (int i = 0; i &lt; arr.length; i++) {
      if (evenIndexValEqualsOddIndexVal(removeElementInArr(arr, i))) {
        count++;
      }
    }
  }
  static int[] removeElementInArr(int[] arr, int index) {
    int[] result = new int[arr.length - 1];
    for (int i = 0, j = 0; i &lt; arr.length &amp;&amp; j &lt; result.length; i++, j++) {
      if (i == index) {
        result[j] = arr[i + 1];
        i++;
      } else {
        result[j] = arr[i];
      }
    }
    return result;
  }
  static boolean evenIndexValEqualsOddIndexVal(int[] arr) {
    int evensum = 0;
    int oddsum = 0;
    for (int i = 0; i &lt; arr.length; i++) {
      if (i % 2 == 0) {
        evensum += arr[i];
      } else {
        oddsum += arr[i];
      }
    }
    return evensum == oddsum &amp;&amp; evensum != 0 &amp;&amp; oddsum != 0;
  }
}

It looks like its runtime is \$O(n^2)\$.
evensum != 0 &amp;&amp; oddsum != 0; is added to satisfy this input [0, 0], but it breaks for input {-5, 7, 0, 5 } whose evensum and oddsum is 0. So, cases like [0,0] are to be dealt with separately.
return evensum == oddsum &amp;&amp; evensum != 0 &amp;&amp; oddsum != 0;


Why can't sums be zero?  With this array ... {-5, 7, 0, 5 } ... if you remove the 7, then the even elements -5 and 5 would sum to zero, and the odd elements 0 also sum to zero, giving a "balanced" array.



Move tests out of loops wherever possible.

    for (int i = 0; i &lt; arr.length; i++) {
      if (i % 2 == 0) {
        evensum += arr[i];
      } else {
        oddsum += arr[i];
      }
    }


Here, with a 1 million element array, i % 2 == 0 is being done 1 million times.  If you summed the even and odd elements separately ...

    for (int i = 0; i &lt; arr.length; i += 2) {
      evensum += arr[i];
    }
    for (int i = 1; i &lt; arr.length; i += 2) {
      oddsum += arr[i];
    }


... you never have to even test i % 2 == 0, which should be a speed improvement.



The above also applies to copying elements in removeElementInArr():

    for (int i = 0, j = 0; i &lt; arr.length &amp;&amp; j &lt; result.length; i++, j++) {
      if (i == index) {
        result[j] = arr[i + 1];
        i++;
      } else {
        result[j] = arr[i];
      }
    }


You know you'll be copying elements up to index, and then copying the elements after index, but you do an i == index inside the loop.  With a million elements, that is a lot of extraneous testing.

    // Copy elements before index:
    for (int i = 0; i &lt; index; i++) {
        result[i] = arr[i];
    }

    // Copy elements after index:
    for (int i = index + 1, j = index; i &lt; arr.length; i++, j++) {
        result[j] = arr[i];
    }


But this is still a lot of manual copying.  The JVM can do the copying for you, a lot more efficiently using System.arraycopy

    System.arraycopy(arr, 0, result, 0, index);
    System.arraycopy(arr, index + 1, result, index, result.length - index);


Now the JVM does all the bound-checking once for each call, instead of two million times when done manually on an array of one million entries.  Much faster.



If you add elements of int[], you may overflow, especially if you have a lot of elements in those arrays.  You may want to use long accumulators.



Algorithmic Improvement

While the above optimizations will speed up the code, the algorithm is still \$O(N^2)\$.  I believe you can improve this to \$O(N)\$.

The problem is you are doing a whole lot of additions, and the partial results of those additions aren't changing.  Given an array of one million entries, when you are deleting the element around index 500,000 or so, the sums of the first 200,000 even indices and the first 200,000 odd indices don't change.

Consider the array:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, ...


If you were asked to find the sum of various spans of elements, say 4rd through 8th, how would you go about doing it?  How about 2nd through 9th? Can you save any work?

If you maintained a list of cumulative sums:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...


The sum of the 4rd through 8th element would be:

                 7 + 9 + 11 + 13 + 15
= (1 + 3 + 5) + (7 + 9 + 11 + 13 + 15) - (1 + 3 + 5)
= (1 + 3 + 5  +  7 + 9 + 11 + 13 + 15) - (1 + 3 + 5)
=                    64                -      9
=               cumulative[8]          -  cumulative[3]


We've preprocessed the input into a cumulative sum array, which is done once \$O(N)\$, and then any subrange sum can be computed in \$O(1)\$ by a simple subtraction.

You've got some issues to work out, such as how and where to store cumulative sums of only the even/odd indices, how to compute the sum of all even indices after an element at index x is removed, etc. But given this is a programming challenge, the implementation is left to student.