Results 1 to 8 of 8
  1. #1
    myst is offline Member
    Join Date
    May 2010
    Posts
    44
    Rep Power
    0

    Default sum of elements in array

    The task is to write a program that returns the index of the cell in the array where the sum of the elements in the array until that cell's element equals the sum of the elements after it until the end. This is for any size array.
    If there is no index like that, return -1.

    for example: 2 1 6 5 4 returns 2 since 2+1+6=5+4 and 6 is in place 2
    however: 3 2 7 returns -1...

    Attempt:

    I tried writing a program that would check the array like this...
    Java Code:
    2+1+6+5 =4,
    2+1+6=5+4, 
    2+1=6+5+4, 
    2=1+6+5+4.

    Java Code:
    public class EqualSum
    {
        public static int equalSum(int[]a){
            int counter=0; // counter saves the values of a[j]
            for (int j=a.length-1; j>0; j--){ 
                if (sum(a, a[j-1]) == (a[j] + counter)) // this checks if the sum from the first cell through the j-1 cell equals the j cell. Since a[j] gets 1 smaller every time, counter keeps the values of the previous a[j]'s...
                    return j-1;
                counter += a[j];    
            }
            return -1;
        }
        
        public static int sum(int[]array, int until){
            int counter=0;
            for (int i=0; i<until; i++)
                counter+= array[i];
            return counter;    
        }    
    
    }
    Can anyone find the error here (or most likely errors...)?

    Thanks.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,000
    Blog Entries
    7
    Rep Power
    20

    Default

    This little problem is so full of preconditions and loop invariant conditions that defining them solves your problem. Here goes:

    suppose that 'left' is the sum of the array elements a[0]+a[1] ... a[j] and 'right' is the sum of the elements a[j+1]+a[j+2] ...

    suppose the length of the array 'a' is 'n'.

    suppose we have a method sum(int[] a) that calculates the sum of all elements in array 'a'.

    For starters we have j= n-1, left= sum(a) and right= 0.

    If left < right we have to return -1 (but we can ignore this condition)

    If left == right we return j

    If left > right we repeat the test after we have adjusted the values as follows:

    left-= a[j]
    right+= a[j]
    j= j-1

    if after the adjustments j < 0 we have to return -1

    All this babbling translates to code as:

    Java Code:
    public static int equalSum(int[] a) {
    	int right = 0; 
    	int left= sum(a);
    		
    	for (int j = a.length - 1; j >= 0; j--) {
    		if (left == right)
    			return j;
    		right+= a[j];
    		left-= a[j];
    
    	}
    	return -1;
    }
    kind regards,

    Jos
    Last edited by JosAH; 07-12-2010 at 08:51 PM.

  3. #3
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    16,574
    Rep Power
    23

    Default

    Can anyone find the error here
    Have you tried debugging it by adding println()s to show how values are computed.

    For example:
    Java Code:
       public static int sum(int[]array, int until){
            int counter=0;
            for (int i=0; i<until; i++)
                counter+= array[i];
            System.out.println("counter=" + counter + ", for until=" + until); // show values
            return counter;    
        }

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,000
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Norm View Post
    Have you tried debugging it by adding println()s to show how values are computed.
    That's just empirism; I like Donald Knuth's remark: "I didn't test it, I just proved it to be correct". ;-)

    kind regards,

    Jos

  5. #5
    al_Marshy_1981 is offline Senior Member
    Join Date
    Feb 2010
    Location
    Waterford, Ireland
    Posts
    748
    Rep Power
    5

    Default

    Quote Originally Posted by JosAH View Post
    That's just empirism; I like Donald Knuth's remark: "I didn't test it, I just proved it to be correct". ;-)

    kind regards,

    Jos
    :D thats ok if you wrote a masterpiece of barely decipherable to the average man piece of work like the art of computer programming or you know if the guy is you :p

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,000
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by al_Marshy_1981 View Post
    :D thats ok if you wrote a masterpiece of barely decipherable to the average man piece of work like the art of computer programming or you know if the guy is you :p
    No, programming should be more science and less engineering; it makes better code and if a bit of math can give a correct answer why try to cook something up by trial and error?

    kind regards,

    Jos

  7. #7
    al_Marshy_1981 is offline Senior Member
    Join Date
    Feb 2010
    Location
    Waterford, Ireland
    Posts
    748
    Rep Power
    5

    Default

    Quote Originally Posted by JosAH View Post
    No, programming should be more science and less engineering; it makes better code and if a bit of math can give a correct answer why try to cook something up by trial and error?

    kind regards,

    Jos
    I agree with your philosophy, I like math but I find it hard to get enthusiastic about it, I think math courses are thought way too abstract and teachers very rarely enthuse about a problems application just it's solution. I tried researching math topics for myself and their uses but even that area seem's fairly limited, any recommendations of books or websites?

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,000
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by al_Marshy_1981 View Post
    I agree with your philosophy, I like math but I find it hard to get enthusiastic about it, I think math courses are thought way too abstract and teachers very rarely enthuse about a problems application just it's solution. I tried researching math topics for myself and their uses but even that area seem's fairly limited, any recommendations of books or websites?
    Agreed, math by itself is dry as straw, but it's a nice toolkit: it helps you solving real world problems; that's what I like about Donald Knuth's books: he abstracts away from a problem and drills down to the bottom of its mathematical foundations, then builds up a solution in the math domain and creates a program for it, solving the original problem. The entire analysis and construction process was in the math domain where only rock hard proofs count, there's no room for speculations, engineering or just plain guessing.

    kind regards,

    Jos

Similar Threads

  1. How to Insert elements into one array
    By zlich in forum New To Java
    Replies: 8
    Last Post: 01-02-2010, 02:37 PM
  2. Looping Array Elements
    By enzyme in forum New To Java
    Replies: 3
    Last Post: 11-26-2009, 04:35 PM
  3. Get value of a String into elements of an Array.
    By mainy in forum New To Java
    Replies: 1
    Last Post: 08-01-2009, 09:17 PM
  4. Replies: 8
    Last Post: 08-27-2008, 10:45 PM
  5. Help with array of elements
    By zoe in forum New To Java
    Replies: 1
    Last Post: 07-24-2007, 05:33 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •