Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

canBalance challenge

Posted on 2016-08-14
34
Medium Priority
?
174 Views
Last Modified: 2016-08-19
Hi,

I am working on below challenge

http://codingbat.com/prob/p158767

I have not understood the description properly

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//i thought since 1+1 is not equal to 2+1 it should be false?
canBalance([2, 1, 1, 2, 1]) → false//i thought since 2+1 is equal to 2+1 it should be true??
canBalance([10, 10]) → true


please advise
0
Comment
Question by:gudii9
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 16
  • 13
  • 5
34 Comments
 
LVL 28

Accepted Solution

by:
rrz earned 1000 total points
ID: 41755907
You are splitting  the first two arrays into three pieces.
front  and middle and back
But, they want us to split the array into two pieces
front and back
[1, 1, 1, 2, 1] can balance  1+1+1 == 2 +1  
[2, 1, 1, 2, 1] can't balance  
[2, 2,1,5] can balance 2+2+1 == 5
My solution has nested for loops . Something like  
for( whole array){
     for( front){ add them}
     for( back){add them}
     if front equals back return true
}
0
 
LVL 7

Author Comment

by:gudii9
ID: 41760265
But, they want us to split the array into two pieces
front and back

break at what index or point? just randomly we can break?
0
 
LVL 28

Expert Comment

by:rrz
ID: 41760437
break at what index or point? just randomly we can break?

They want us to split the array into two parts that balance.
[1, 1, 1, 2, 1] can balance  1+1+1 == 2 +1
[2, 2,1,5] can balance 2+2+1 == 5  
We are search for the condition  that front == back
So, we have to search for the balance point.  
for( each split point in array){
      for( each element from first to split ){ add them up}
      for( each element from split to last){add them up}
      if front equals back return true
 }
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 101

Assisted Solution

by:mlmcc
mlmcc earned 1000 total points
ID: 41760934
Is there a way you can determine immediately that it is not possible?
For it to be possible the sum of the full array must be ?????

If it is possible then there is no need to search
Sum from the front of the array until FrontSum = ??????

mlmcc
0
 
LVL 28

Expert Comment

by:rrz
ID: 41761194
canBalance([2, 3, 4, 1, 2]) → false
0
 
LVL 7

Author Comment

by:gudii9
ID: 41761886
psedo code of logic approach is

1. loop through array from start
2. find the sum of left hand side
3. loop from backwards similar way
4. find the sum from right hand side
5. if both above sums equal return true
6. else return false.

below failing few tests . please advise
public boolean canBalance(int[] nums) {
		  for (int i = 0; i < nums.length; i++) {
			  int leftTotal=0;
			  leftTotal=leftTotal+nums[i];
			  for (int j = nums.length-1; j >i; j--) {
				  int rightTotal=0;
				  rightTotal=rightTotal+nums[i];
				  if(rightTotal==leftTotal){
					  return true;
				  }
				
			}
			
		}
		  
		  return false;
		}

Open in new window


Expected      Run            
canBalance([1, 1, 1, 2, 1]) → true      true      OK      
canBalance([2, 1, 1, 2, 1]) → false      true      X      
canBalance([10, 10]) → true      true      OK      
canBalance([10, 0, 1, -1, 10]) → true      true      OK      
canBalance([1, 1, 1, 1, 4]) → true      true      OK      
canBalance([2, 1, 1, 1, 4]) → false      true      X      
canBalance([2, 3, 4, 1, 2]) → false      true      X      
canBalance([1, 2, 3, 1, 0, 2, 3]) → true      true      OK      
canBalance([1, 2, 3, 1, 0, 1, 3]) → false      true      X      
canBalance([1]) → false      false      OK      
canBalance([1, 1, 1, 2, 1]) → true      true      OK      
other tests
X

public class CanBalance {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] ar={1,1,1,2,1};
		System.out.println("canBalance value is--->"+canBalance(ar));

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


}

Open in new window


canBalance value is--->true
0
 
LVL 28

Expert Comment

by:rrz
ID: 41761985
When things aren't working as I planned, I add debug statements. That way I can see what is going on during the execution of my code.  For example,  
public class CanBalance {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] ar={1,1,1,2,1};
		System.out.println("canBalance value is--->"+canBalance(ar));

	}
	
	public static boolean canBalance(int[] nums) {
		  for (int i = 0; i < nums.length; i++) {
			  int leftTotal=0;
			  leftTotal=leftTotal+nums[i];
			  System.out.println("i is " + i + " leftTotal is " + leftTotal);
			  for (int j = nums.length-1; j >i; j--) {
				  int rightTotal=0;
				  rightTotal=rightTotal+nums[i];
				  System.out.println("j is " + j + " rightTotal is " + leftTotal);
				  if(leftTotal==rightTotal){
					  return true;
				  }
				
			}
			
		}  
		  return false;
		}
}

Open in new window

The output is
i is 0 leftTotal is 1
j is 4 rightTotal is 1
canBalance value is--->true  

Now we see what the machine is doing. It is just comparing the first element with the first element. Which is true for this particular input.
Now let's change input to {1, 2, 3, 1, 0, 1, 3}
The output now is
i is 0 leftTotal is 1
j is 6 rightTotal is 1
canBalance value is--->true    

With the debug statements I have added, the code should print the totals in every iteration. Your code just  stops after a single iteration.  Another thing we can see from the second test, this statement
rightTotal=rightTotal+nums[i];

Open in new window

is wrong. rightTotal should have equal to 3(at that point).  You have i where you should have j.
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 41762507
No your issue is when you reset the totals to 0.
You are resetting the total to 0 each time through the loop.
The loops should calculate the total from that direction so the reset should be ????

mlmcc
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762595
public boolean canBalance(int[] nums) {
		  int leftTotal=0;
		  int rightTotal=0;
		  for (int i = 0; i < nums.length; i++) {
			
			  leftTotal=leftTotal+nums[i];
			 // System.out.println("i is " + i + " leftTotal is " + leftTotal);
			  for (int j = nums.length-1; j >i; j--) {
				 
				  rightTotal=rightTotal+nums[j];
				//  System.out.println("j is " + j + " rightTotal is " + rightTotal);
				  if(leftTotal==rightTotal){
					  return true;
				  }
				
			}
			
		}
		  
		  return false;
		}

Open in new window


passed couple of more tests
Expected      Run            
canBalance([1, 1, 1, 2, 1]) → true      true      OK      
canBalance([2, 1, 1, 2, 1]) → false      false      OK      
canBalance([10, 10]) → true      true      OK      
canBalance([10, 0, 1, -1, 10]) → true      true      OK      
canBalance([1, 1, 1, 1, 4]) → true      false      X      
canBalance([2, 1, 1, 1, 4]) → false      false      OK      
canBalance([2, 3, 4, 1, 2]) → false      true      X      
canBalance([1, 2, 3, 1, 0, 2, 3]) → true      false      X      
canBalance([1, 2, 3, 1, 0, 1, 3]) → false      false      OK      
canBalance([1]) → false      false      OK      
canBalance([1, 1, 1, 2, 1]) → true      true      OK      
other tests
OK      

public class CanBalance {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//int[] ar={1,1,1,2,1};
		//System.out.println("canBalance value is--->"+canBalance(ar));
		
		//2, 1, 1, 2, 1
		int[] ar1={1, 2, 3, 1, 0, 1, 3};
		System.out.println("canBalance value is--->"+canBalance(ar1));

	}
	
	public static boolean canBalance(int[] nums) {
		  int leftTotal=0;
		  int rightTotal=0;
		  for (int i = 0; i < nums.length; i++) {
			
			  leftTotal=leftTotal+nums[i];
			  System.out.println("i is " + i + " leftTotal is " + leftTotal);
			  for (int j = nums.length-1; j >i; j--) {
				 
				  rightTotal=rightTotal+nums[j];
				  System.out.println("j is " + j + " rightTotal is " + rightTotal);
				  if(leftTotal==rightTotal){
					  return true;
				  }
				
			}
			
		}
		  
		  return false;
		}


}

Open in new window


i is 0 leftTotal is 1
j is 6 rightTotal is 3
j is 5 rightTotal is 4
j is 4 rightTotal is 4
j is 3 rightTotal is 5
j is 2 rightTotal is 8
j is 1 rightTotal is 10
i is 1 leftTotal is 3
j is 6 rightTotal is 13
j is 5 rightTotal is 14
j is 4 rightTotal is 14
j is 3 rightTotal is 15
j is 2 rightTotal is 18
i is 2 leftTotal is 6
j is 6 rightTotal is 21
j is 5 rightTotal is 22
j is 4 rightTotal is 22
j is 3 rightTotal is 23
i is 3 leftTotal is 7
j is 6 rightTotal is 26
j is 5 rightTotal is 27
j is 4 rightTotal is 27
i is 4 leftTotal is 7
j is 6 rightTotal is 30
j is 5 rightTotal is 31
i is 5 leftTotal is 8
j is 6 rightTotal is 34
i is 6 leftTotal is 11
canBalance value is--->false



Trying to fox them too
0
 
LVL 28

Expert Comment

by:rrz
ID: 41762611
Thank you, for inserting debug statements. Now you can see that  you need to fix the reset problem as pointed out by mlmcc
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762617
i like debug statement with with both i and totals which gives clear picture.


i is 0 leftTotal is 1
j is 4 rightTotal is 4
j is 3 rightTotal is 5
j is 2 rightTotal is 6
j is 1 rightTotal is 7
i is 1 leftTotal is 2
j is 4 rightTotal is 11



issue now is when i=i then jstarts from 4 again and the total needs to reset to 0 and start total with 5 then 5 for j=3 etc...which is not happening now?
0
 
LVL 28

Expert Comment

by:rrz
ID: 41762620
I can see a difference between my code and yours. In my code I have one for loop to add left and another for loop to add right. Those two for loops are nested in another for loop.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762625
can we do with 2 for loops instead of 3?
0
 
LVL 28

Expert Comment

by:rrz
ID: 41762627
Please look at my pseudo code in my first comment.
0
 
LVL 28

Expert Comment

by:rrz
ID: 41762630
can we do with 2 for loops instead of 3?
I don't know. Maybe some expert will show us how.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762637
My solution has nested for loops . Something like  
for( whole array){
     for( front){ add them}
     for( back){add them}
     if front equals back return true
}

i see it. i am still thinking iif there is a way to fix with 2 loops if yes 3 loops unnecessary right?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762653
int leftTotal=0;
              int rightTotal=0;

do i need to define above two on top of outer for loop ( for (int i = 0; i < nums.length; i++) {      )or one on top of outer for loop and another one(int rightTotal=0;) on top of inner for loop(  for (int j = nums.length-1; j >i; j--) {)
0
 
LVL 28

Expert Comment

by:rrz
ID: 41762654
3 loops unnecessary right?
I don't know.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762669
public boolean canBalance(int[] nums) {
		  int leftTotal=0;		 
		
		  for (int i = 0; i < nums.length; i++) {			
			  leftTotal=leftTotal+nums[i];
			 // System.out.println("i is " + i + " leftTotal is " + leftTotal);
			    int rightTotal=0;
			  for (int j = nums.length-1; j >i; j--) {				 
				  rightTotal=rightTotal+nums[j];
				  //System.out.println("j is " + j + " rightTotal is " + rightTotal);
			  }
				  if(leftTotal==rightTotal){
					  return true;
				  }				
			}			
				  
		  return false;
		}

Open in new window


above passed all tests. I have to take out the if loop from inner for loop and also place rightTotal above inner for loop as below

int rightTotal=0;
                    for (int j = nums.length-1; j >i; j--) {
0
 
LVL 28

Expert Comment

by:rrz
ID: 41762673
do i need to define ....
 I don't know. I can't really understand your code(thinking).   My thoughts :
in each iteration of outer for loop
add left
add right
if equal then break out
else reset
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762685
public class CanBalance {
	public static void main(String[] args) {
	
		int[] ar1={2, 1, 1, 2, 1};
		System.out.println("canBalance value is--->"+canBalance(ar1));
	}	
	public static boolean canBalance(int[] nums) {
		  int leftTotal=0;		 
		  
		  for (int i = 0; i < nums.length; i++) {			
			  leftTotal=leftTotal+nums[i];
			  System.out.println("i is " + i + " leftTotal is " + leftTotal);
			  int rightTotal=0;
			  for (int j = nums.length-1; j >i; j--) {				 
				  rightTotal=rightTotal+nums[j];
				  System.out.println("j is " + j + " rightTotal is " + rightTotal);
			  }
				  if(leftTotal==rightTotal){
					  return true;
				  }				
			}			
				  
		  return false;
		}
}

Open in new window


i is 0 leftTotal is 2
j is 4 rightTotal is 1
j is 3 rightTotal is 3
j is 2 rightTotal is 4
j is 1 rightTotal is 5
i is 1 leftTotal is 3
j is 4 rightTotal is 1
j is 3 rightTotal is 3
j is 2 rightTotal is 4
i is 2 leftTotal is 4
j is 4 rightTotal is 1
j is 3 rightTotal is 3
i is 3 leftTotal is 6
j is 4 rightTotal is 1
i is 4 leftTotal is 7
canBalance value is--->false
any improvements, modifications, refinement to above code? how does your code looks like?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762690
in each iteration of outer for loop
add left
start iteration of inner for loop
add right
if equal then return true
else return false
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 41762693
YOu need to test for equality after each time you add the right value.

mlmcc
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762699
YOu need to test for equality after each time you add the right value.

is that is reason why

 I have to take out the if loop from inner for loop and also place rightTotal above inner for loop(not above outer for loop) as below??

int rightTotal=0;                     for (int j = nums.length-1; j >i; j--) {
0
 
LVL 28

Expert Comment

by:rrz
ID: 41762708
above passed all tests
Great! I am glad that you stayed with your own  idea.
0
 
LVL 28

Expert Comment

by:rrz
ID: 41762728
Your code is better than mine. We learn from each other.
public class CanBalance {
	public static void main(String[] args) {
		int[] ar={4, 2, 3, 3};
		System.out.println("canBalance value is--->"+canBalance(ar));
	}
    public static boolean canBalance(int[] nums) {
		boolean result = false;
        int front = 0;
        int back = 0;
		for(int i = 0; i < nums.length; i++){
			for(int f = 0; f < i + 1 ; f++){
				front += nums[f];
				System.out.println("f is " + f + " front is " + front);
			}
			for(int b = i + 1; b < nums.length ; b++){
				back += nums[b];
				System.out.println("b is " + b + " back is " + back);
			}
			if(front == back){
				result = true;
				break;
			}
			else{
				front = 0;
				back = 0;
			}
		}
		return result;
    }
}

Open in new window

 Output was  
f is 0 front is 4
b is 1 back is 2
b is 2 back is 5
b is 3 back is 8
f is 0 front is 4
f is 1 front is 6
b is 2 back is 3
b is 3 back is 6
canBalance value is--->true  

I stubbornly held to my first thoughts. I wastefully added the front(left) over and over. Your way is better.
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 41762758
iteration of outer for loop
     add left
     start iteration of inner for loop
            add right
            if equal then return true
     Loop inner
Loop outer
return false

mlmcc
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762764
iteration of outer for loop
     add left
     start iteration of inner for loop
            add right
            if equal then return true
     Loop inner
Loop outer
return false


how looping is different from iteration? i am thinking both same?
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 41762776
Same.  Just different terms.  Loop inner means return to start of iteration (loop) for next.

Only difference with your code is where you test for equality

mlmcc
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762811
Only difference with your code is where you test for equality

how your code looks like? did you use if loop inside inner for loo?
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762818
public boolean canBalance(int[] nums) {
		  int leftTotal=0;	
		   int rightTotal=0;
		
		  for (int i = 0; i < nums.length; i++) {			
			  leftTotal=leftTotal+nums[i];
			 // System.out.println("i is " + i + " leftTotal is " + leftTotal);
			 //   int rightTotal=0;
			  for (int j = nums.length-1; j >i; j--) {				 
				  rightTotal=rightTotal+nums[j];
				  //System.out.println("j is " + j + " rightTotal is " + rightTotal);
			  }
				  if(leftTotal==rightTotal){
					  return true;
				  }				
			}			
				  
		  return false;
		}

Open in new window


Expected      Run            
canBalance([1, 1, 1, 2, 1]) → true      false      X      
canBalance([2, 1, 1, 2, 1]) → false      false      OK      
canBalance([10, 10]) → true      true      OK      
canBalance([10, 0, 1, -1, 10]) → true      true      OK      
canBalance([1, 1, 1, 1, 4]) → true      false      X      
canBalance([2, 1, 1, 1, 4]) → false      false      OK      
canBalance([2, 3, 4, 1, 2]) → false      false      OK      
canBalance([1, 2, 3, 1, 0, 2, 3]) → true      false      X      
canBalance([1, 2, 3, 1, 0, 1, 3]) → false      false      OK      
canBalance([1]) → false      false      OK      
canBalance([1, 1, 1, 2, 1]) → true      false      X      
other tests
OK      

why above code fails some tests if i move rightSum initialization line to the top of outer for loop rather than inner for loop??
int rightTotal=0;
		
		  for (int i = 0; i < nums.length; i++) {

Open in new window

0
 
LVL 28

Expert Comment

by:rrz
ID: 41762829
why above code fails some tests if i move rightSum initialization line to the top of outer for loop rather than inner for loop??
because you are not resetting the total value.
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762843
i is 0 leftTotal is 2
j is 4 rightTotal is 1
j is 3 rightTotal is 3
j is 2 rightTotal is 4
j is 1 rightTotal is 5
i is 1 leftTotal is 3
j is 4 rightTotal is 1
j is 3 rightTotal is 3
j is 2 rightTotal is 4
i is 2 leftTotal is 4
j is 4 rightTotal is 1
j is 3 rightTotal is 3
i is 3 leftTotal is 6
j is 4 rightTotal is 1
i is 4 leftTotal is 7
canBalance value is--->false


I see difference. As given below right Sum never resetted back to 0 if it is above outer loop. where as resetted perfectly if above inner for  loop producing correct output as above



i is 0 leftTotal is 2
j is 4 rightTotal is 1
j is 3 rightTotal is 3
j is 2 rightTotal is 4
j is 1 rightTotal is 5
i is 1 leftTotal is 3
j is 4 rightTotal is 6
j is 3 rightTotal is 8
j is 2 rightTotal is 9
i is 2 leftTotal is 4
j is 4 rightTotal is 10
j is 3 rightTotal is 12
i is 3 leftTotal is 6
j is 4 rightTotal is 13
i is 4 leftTotal is 7
canBalance value is--->false
0
 
LVL 7

Author Comment

by:gudii9
ID: 41762882
why above code fails some tests if i move rightSum initialization line to the top of outer for loop rather than inner for loop??
because you are not resetting the total value.

now it is clear.

If given array is {1,1,1,1,4}

i   legtTotal  j    rightTotal(// i wonder how to draw a table in EE?)
0   1              4   4
                      3   5
                      2   6
                      1   7

1   2               4   4//here we need 4 value (which comes if i initialize rightTotal on top of inner for loop as it resetted when j inner loop start over triggered by increment of i from 0 to 1 etc...not 11 which comes if initializeat top of outer for loop as it keep on adding total till outer i loop completes.

Also if (leftTotal == rightTotal) check still inside outer for loop even though it is outside inner for loop which is whagt we wanted(to check each value of i we are finding all rightTotal values comparing with leftTotals.

i am closing this now
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
Make the most of your online learning experience.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
Suggested Courses

610 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question