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 is O(n^2), but you can do it in O(n)!
ReplyDeletepublic boolean canBalance(int[] nums) {
int rightSum = 0;
for (int i=0; i<nums.length; i++) {
rightSum += nums[i];
}
int leftSum = 0;
for (int i=0; i<nums.length; i++) {
leftSum += nums[i];
rightSum -= nums[i];
if (leftSum == rightSum) return true;
}
return false;
}
This is very clever, nice:)
Deletevery nice one)
Delete2 1 1 0 2
Deletewhat is the output for this array??
public boolean canBalance(int[] nums) {
ReplyDeleteint sum1=0;
int sum2=0;
for(int i=0; i< nums.length ; i++)
{
sum1=0;
sum2=0;
for(int j=0 ; j<=i ; j++)
sum1=sum1+nums[j];
for(int k=i+1; k<nums.length ; k++)
sum2=sum2+nums[k];
if(sum1==sum2) return true ;
else continue;
}
return false;
}
I did the same logic as you, but I didn't reset the sum1 and sum2, so get wrong. Thank you for the post and let me find where I am wrong
Deletepublic boolean canBalance(int[] nums) {
ReplyDeleteint left = 0;
int right = 0;
for (int i = 0, j = nums.length - 1; i <= j;) {
if (left < right) {
left += nums[i++];
} else {
right += nums[j--];
}
}
return (left == right);
}
Oops.
ReplyDeleteThat passes all the test cases, but fails for [4, 5, -2, 3, 8], or other cases where the "deciding value" is negative.
Revision:
public boolean canBalance(int[] nums) {
int left = 0;
int right = 0;
for (int i = 0, j = nums.length - 1; i <= j;) {
if (left < right) {
if (nums[i] > 0) {
left += nums[i++];
} else {
right += nums[j--];
}
} else {
if (nums[i] > 0) {
right += nums[j--];
} else {
left += nums[i++];
}
}
}
return (left == right);
}
public boolean canBalance(int[] nums) {
ReplyDeleteint count1=0;
int count2=0;
int total=0;
for(int i=0; i<nums.length; i++)
total+=nums[i];
if(total%2 != 0) return false;
else total/=2;
for(int i=0; i<nums.length; i++){
count1+=nums[i];
if(count1==total) break;
}
count2=2*total-count1;
return count1==count2;
}
public boolean canBalance(int[] nums) {
ReplyDelete//split array at each location in the array
for(int i = 1; i < nums.length; i++){
//add up sums on the left and right sides of the split
int sumLeft = 0;
int sumRight = 0;
for(int n = 0; n < i; n++){
sumLeft += nums[n];
}
for(int m = i; m < nums.length; m++){
sumRight += nums[m];
}
if(sumLeft == sumRight)
return true;
}
return false;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint som=0;
for (int n:nums)
som+=n;
for (int i=0, lsom=0 ; i<nums.length && lsom*2<som ; ++i)
if ((lsom += nums[i]) * 2 == som) return true;
return false;
}
Solved almost same:
Deletepublic boolean canBalance(int[] nums) {
long sum = 0;
long half = 0;
for (int num : nums) {
sum += (long) num;
}
for (int i = 0; half < sum/2.0 && i < nums.length; i++) {
half += (long) nums[i];
}
return half == sum/2.0;
}
var array =[4,5,-2,3,8];
ReplyDeletevar sum = 0;
var sum2 = 0;
var count = Math.round(array.length/2);
for (var i = 0; i<count;i++) {
sum += array[i];
}
for (var i = count ; i<=array.length-1;i++ ) {
sum2 += array[i];
}
if (sum == sum2) {
document.write("True")
}
else {
document.write("False")
}
public boolean canBalance(int[] nums) {
ReplyDeleteint sum =0;
float half =0, tempSum = 0;
for(int num : nums){
sum += num;
}
half = sum/2;
if(sum%2 == 0){
for(int i=0;i<nums.length;i++){
tempSum += nums[i];
if(tempSum==half){
return true;
}
}
}
return false;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint number = nums[0], val = 0;
boolean flag = false;
for (int i = 1; i < nums.length; i++){
for (int j =i; j<nums.length; j++){
val += nums[j];
if (number == val && j == nums.length-1)
flag = true;
}
val =0;
number+=nums[i];
}
return flag;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint number = nums[0], val = 0;
for (int i = 1; i < nums.length; i++){
for (int j =i; j<nums.length && val < number; j++){
val += nums[j];
if (number == val && j == nums.length-1)
return true;
}
val =0;
number+=nums[i];
}
return false;
}
def can_balance(arr):
ReplyDeletetotal_sum = sum(arr)
left_sum = arr[0]
if total_sum % 2 != 0:
return False
for i in range(1, len(arr)):
if total_sum-left_sum == (total_sum/2):
return True
left_sum += arr[i]
return False
public boolean canBalance(int[] nums) {
ReplyDeleteint i=0;
int leftSum = 0;
int rightSum = 0;
while(i<nums.length){
for(int j=0;j<i;j++){
leftSum = leftSum + nums[j];
}
for(int k=i;k<nums.length;k++){
rightSum = rightSum + nums[k];
}
if(leftSum==rightSum) return true;
leftSum = 0;
rightSum = 0;
i++;
}
return false;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint sum = 0;
int sumMinus = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
for (int i = 0; i < nums.length; i++) {
if (sumMinus == sum) return true;
sumMinus += nums[i];
sum -= nums[i];
}
return false;
}
This is in O(n^2) there is another solution but in O(n):
ReplyDeletepublic boolean canBalance(int[] nums) {
int sum = 0;
for (int i = 0; i < nums.length; i++)
sum += nums[i];
int currentSum = 0;
for (int i = 0; i < nums.length; i++)
{
currentSum += nums[i];
if (sum - currentSum == currentSum)
return true;
}
return false;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint left = 0;
int right=0;
for(int k=0;k<nums.length; k++) {
right+=nums[k];
}
for(int i=0; i<nums.length-1; i++) {
if(left!=right) {
left+=nums[i];
right-=nums[i];
}
}
return left==right;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint first = 0;
int second = 0;
for(int i = 0; i < nums.length; i++) {
second += nums[i];
}
for(int i = 0; i < nums.length; i++) {
first += nums[i];
second -= nums[i];
if(first == second) {
return true;
}
}
return false;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint sum = 0;
int halfSum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (sum % 2 == 0) {
for (int j = 0; j < nums.length; j++) {
halfSum += nums[j];
if (halfSum == sum / 2) {
return true;
}
}
return false;
}
return false;
}
public static boolean canBalance(int[] nums) {
ReplyDeleteint sl = nums[0], sr = 0, p = 1;
for(int i = 1; i < nums.length; i++) sr += nums[i];
while(p < nums.length) {
if(sl >= sr) break;
sl += nums[p];
sr -= nums[p];
p++;
}
return (sl == sr);
}
public boolean canBalance(int[] nums) {
ReplyDeleteint sumOne = 0;
int sumTwo = 0;
for (int i = 0; i < nums.length - 1; i++)
{
sumOne += nums[i];
for (int j = i + 1; j < nums.length; j++)
{
sumTwo += nums[j];
}
if (sumOne == sumTwo)
{
return true;
}
else
{
sumTwo = 0;
}
}
return false;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint sum = 0;
int halfSum = 0;
boolean isBalance = false;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
for (int i = 0; i < nums.length; i++) {
halfSum += nums[i];
if (halfSum * 2 == sum) {
isBalance = true;
break;
}
}
return isBalance;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint rightSum = 0;
int leftSum =0;
for (final int num: nums) {
rightSum += num;
}
for (final int num: nums) {
leftSum += num;
rightSum -= num;
if(leftSum == rightSum){
return true;
}
}
return false;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint sumLeft = 0, sumRight = 0,i = 0, j = nums.length - 1, k = 0, condition = 0;
while (condition != nums.length) {
if (sumLeft < sumRight) {
sumLeft += nums[i];
i++;
} else if (sumLeft > sumRight) {
sumRight += nums[j];
j--;
k++;
} else {
if (i + k != nums.length-1) {
sumLeft += nums[i];
sumRight += nums[j];
i++;
j--;
k++;
}
else{
return false;
}
}
condition = i+k;
}
return sumRight == sumLeft;
}
Its a solution with 1 cycle!
Deleteraaly?
Deletedef canBalance(n):
s = 0
for i in range(len(n)):
if sum(n[0:i]) == sum(n[i:len(n)]):
return True
return False
I have a pretty elegant solution
ReplyDeletepublic boolean canBalance(int[] nums) {
for(int i = 0; i < nums.length; i++) {
int sumLeft = 0;, sumRight = 0;
for (int j = 0; j < i; j++)
sumLeft += nums[j];
for (int k = i; k < nums.length; k++)
sumRight += nums[k];
if (sumLeft == sumRight) return true;
}
return false;
}
public boolean canBalance(int[] nums) {
ReplyDeleteint splitPoint=nums.length-1;
if(nums.length==1 )return false;
while(splitPoint!=0 ){
int sum1=0;
int sum2=0;
for(int i=0;i<splitPoint;i++){
sum1+=nums[i];
}
for(int j=splitPoint;j<nums.length;j++){
sum2+=nums[j];
}
if(sum1==sum2)return true;
splitPoint--;
}
return false;
}
public boolean canBalance(int[] nums) {
ReplyDeletedouble sum= Arrays.stream(nums).sum();
int sumHalf=0;
for(int i=0; i<nums.length;i++) {
sumHalf+=nums[i];
if(sumHalf==sum/2) {
return true;
}
}
return false;
}
int j = 0;
ReplyDeleteint sum = 0;
int sumSplit = 0;
for(int i = 0; i < nums.length; i++)
sum += nums[i];
while(keepRunning && j < nums.length)
{
sumSplit += nums[j];
if(sum - sumSplit == sumSplit)
return true;
j++;
}
return false;
This was mine. Just get the total sum, then see if when you keep adding terms from the array and subtract the new sum from the original you get the new sum back!