Java > Array-3 > canBalance (CodingBat Solution)

Problem:

Given a non-empty array, 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.

canBalance({1, 1, 1, 2, 1}) → true
canBalance({2, 1, 1, 2, 1}) → false
canBalance({10, 10}) → true


Solution:

public boolean canBalance(int[] nums) {
  int lSum = 0;
  
  for (int i = 0; i < nums.length; i++) {
    lSum += nums[i];
    int rSum = 0;
    for (int j = nums.length-1; j > i; j--) {
      rSum += nums[j];
    }
    if (rSum == lSum)
      return true;
  }
  return false;
}

3 comments:

  1. UnknownJanuary 18, 2015 at 1:06 AM

    This code ends up being O(n^2) time in the worst case which is unacceptable usually.

    Check out this:
    public boolean canBalance(int[] nums) {
    int sum = 0;
    for(int i = 0; isum/2) return false;
    }
    return true;
    }

    Two consecutive loops, and the second loop is not always done so the run time is O(n) or O(2n)

    ReplyDelete
  2. UnknownJanuary 18, 2015 at 1:14 AM

    public boolean canBalance(int[] nums) {
    int sum = 0;
    for(int i = 0; isum/2) return false;
    }
    return true;
    }

    ReplyDelete
  3. AnonymousJune 3, 2021 at 3:51 PM

    public boolean right

    ReplyDelete