title: Algorithm Code Optimization: Find the Equilibirum: Find an index in an array such that its prefix sum equals its suffix sum
body: <p><strong>Here's my Task Description:</strong></p>
  
  <p>A zero-indexed array A consisting of N integers is given. </p>
  
  <p>An equilibrium index of this array is any integer P such that 0 ≤ P &lt; N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e. 
  A[0] + A<a href="https://i.stack.imgur.com/dzuWY.png" rel="nofollow noreferrer">1</a> + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].</p>
  
  <p>Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.
  For example, consider the following array A consisting of N = 8 elements:</p>
  
  <pre><code>A[0] = -1
  A[1] =  3
  A[2] = -4
  A[3] =  5
  A[4] =  1
  A[5] = -6
  A[6] =  2
  A[7] =  1
  
  P = 1 is an equilibrium index of this array, because:
  •   A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
  P = 3 is an equilibrium index of this array, because:
  •   A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
  P = 7 is also an equilibrium index, because:
  •   A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0
  </code></pre>
  
  <p>and there are no elements with indices greater than 7.
      P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P &lt; N.</p>
  
  <p>Write a function:
  int solution(NSMutableArray *A);
  that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. </p>
  
  <p>The function should return −1 if no equilibrium index exists.
  For example, given array A shown above, the function may return 1, 3 or 7, as explained above.</p>
  
  <p>Assume that:
      •   N is an integer within the range [0..100,000];
      •   each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].</p>
  
  <p>Complexity:
      •   expected worst-case time complexity is O(N);
      •   expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).</p>
  
  <p>Elements of input arrays can be modified.</p>
  
  <p><strong><em>Here's my Solution for the problem in Objective C:</em></strong></p>
  
  <pre><code>-(int)solution:(NSArray *) A{
  for (int i=0; i&lt;A.count; i++) {
  
      NSUInteger backwardsTotal = 0;
      if (i &gt; 0) {
          for (int k=0; k&lt;i; k++) {
              NSNumber *kValue = A[k];
              backwardsTotal += kValue.intValue;
          }
      }
  
      NSUInteger forwardTotal = 0;
      for (int j=i+1; j&lt;A.count; j++) {
          NSNumber *jValue = A[j];
          forwardTotal += jValue.intValue;
      }
  
      if (backwardsTotal == forwardTotal) {
          return i;
      }
  }
  
  return -1;
  }
  </code></pre>
  
  <p>How can i optimise this solution?</p>
  
  <p>Changes made to the method as per @Nikki comments:</p>
  
  <pre><code>-(int)solution:(NSArray *) A{
  NSUInteger a = 0, b = 0;
  
  for (int i=0; i&lt;A.count; i++) {
      NSNumber *iValue = A[i];
      b += iValue.intValue;
  }
  NSLog(@"Total: b: %ld", b);
  
  for (int k=0; k&lt;A.count; k++) {
      NSNumber *kValue = A[k];
      b -= kValue.intValue;
  
      NSLog(@"b: %ld", b);
      NSLog(@"a: %ld", a);
  
      if (a == b)
          return k;
  
      a += kValue.intValue;
  
  }
  
  return -1;
  }
  </code></pre>
  
  <p>I am testing the above code as follows:</p>
  
  <pre><code>//    NSArray *array = @[@"-3", @"0", @"3"];
  NSArray *array = @[@"-2", @"4", @"-5", @"6", @"1", @"-6", @"2", @"1"];
  NSUInteger one = [self solution:array];
  NSLog(@"one: %ld", one);//returns 7
  </code></pre>
  
  <p>The solution seems to work better.
  But still, it is not perfect and uses O(N**2) time complexity.
  And also there are Timeout errors in other Performance tests.</p>
  
  <p>Screenshots below:</p>
  
  <p><a href="https://i.stack.imgur.com/dzuWY.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/dzuWY.png" alt="Performance Test1"></a></p>
  
  <p><a href="https://i.stack.imgur.com/r6xoK.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/r6xoK.png" alt="Performance Test2"></a></p>
  
  <p><a href="https://i.stack.imgur.com/HIEah.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/HIEah.png" alt="Performance Test3"></a></p>
  
  <p>Can this be still optimized?</p>