Thread: sum of elements in array

1. Member
Join Date
May 2010
Posts
44
Rep Power
0

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. 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. 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. Originally Posted by Norm
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. Senior Member
Join Date
Feb 2010
Location
Waterford, Ireland
Posts
748
Rep Power
7
Originally Posted by JosAH
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. Originally Posted by al_Marshy_1981
: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. Senior Member
Join Date
Feb 2010
Location
Waterford, Ireland
Posts
748
Rep Power
7
Originally Posted by JosAH
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. Originally Posted by al_Marshy_1981
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

Posting Permissions

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