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;
}