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;
}
This code ends up being O(n^2) time in the worst case which is unacceptable usually.
ReplyDeleteCheck 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)
public boolean canBalance(int[] nums) {
ReplyDeleteint sum = 0;
for(int i = 0; isum/2) return false;
}
return true;
}
public boolean right
ReplyDelete