Friday, May 6, 2011

Finding the position in an array where right side sum is equal to left side sum

Code is pretty much simple.
So here is the code for the problem:
/**
 * @author Dharmvir Singh 
 * This program finds the position in an array where sum of left
 * side is equal to sum of right side excluding the position. If
 * position doesn't exist return -1.
 */
public class FindPosition {
 public static void main(String[] args) {
  // int a[] = { 1, 2, 3, 2, 1 };
  int a[] = { -1, 2, -3, 6, -5 };
  int sumLeft = a[0], flag = 0, sumRight = 0;
  int arrayLength = a.length;
  // Assume that 1st position is the desired position and so finding the
  // right side sum
  for (int i = 2; i < arrayLength; i++) {
   sumRight += a[i];
  }
  /*
   * Now we will check if our assumption is correct that if a[1] position
   * and if not assume that a[2] is the correct one and so on.. last
   * position to check will be (a.length-1)
   */
  int i;
  for (i = 1; i < (arrayLength - 1); i++) {
   if (sumLeft == sumRight) {
    break;
   }
   sumLeft += a[i];
   sumRight -= a[i + 1];
  }

  if (i < arrayLength - 1) {
   System.out.println("Pos is " + i + "  sum is: " + sumLeft);
  } else {
   System.out.println("No post");
  }
 }
}
Related Posts

Happy Coding.

1 comment: