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:
01 | public boolean canBalance( int [] nums) { |
02 | int lSum = 0 ; |
03 | |
04 | for ( int i = 0 ; i < nums.length; i++) { |
05 | lSum += nums[i]; |
06 | int rSum = 0 ; |
07 | for ( int j = nums.length- 1 ; j > i; j--) { |
08 | rSum += nums[j]; |
09 | } |
10 | if (rSum == lSum) |
11 | return true ; |
12 | } |
13 | return false ; |
14 | } |
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