Zero Sum

[ttoboobz]

Hi everyone,

I need help for my project in my Java Programming 1 subject. I really don't have an idea on how to go about with this problem. I have started building the code for the CLASS, but didn't bother to post it, cause everytime after I declare the main method, my mind freezes, that's why I decided to ask for your help. This is the problem anyway...

Consider the sequence of digits from 1 through N (where N = 9) in increasing order 1 2 3 4 5 . . . .N, and insert a (+) for addition or a (-) for subtraction or a () [blank] to run the digits together. Now sum the result and see if you get zero.

Write a program that will find all sequences of length N that produces a ZERO SUM.

Test Case 1

Input
7

Output
1 + 2 - 3 + 4 - 5 - 6 + 7 = 0
1 + 2 - 3 - 4 + 5 + 6 - 7 = 0
1 - 2 + 3 + 4 - 5 + 6 - 7 = 0
1 - 2 - 3 - 4 - 5 + 6 + 7 = 0
1 - 23 + 4 + 5 + 6 + 7 = 0
1 - 23 + 45 + 67 = 0


Test Case 2

Input
8

Output
1 + 2 + 3 + 4 - 5 - 6 - 7 + 8 = 0
1 + 2 + 3 - 4 + 5 - 6 + 7 - 8 = 0
1 + 2 - 3 + 4 + 5 + 6 - 7 - 8 = 0
1 + 2 - 3 - 4 - 5 - 6 + 7 + 8 = 0
1 + 23 - 45 + 6 + 7 + 8 = 0
1 - 2 + 3 - 4 - 5 + 6 - 7 + 8 = 0
1 - 2 - 3 + 4 + 5 - 6 - 7 + 8 = 0
1 - 2 - 3 + 4 - 5 + 6 + 7 - 8 = 0
1 - 23 - 4 + 5 + 6 + 7 + 8 = 0
12 - 34 - 56 + 78 = 0

You may test this program by entering the integer from the keyboard.


Thanks, your help is highly appreciated...

[sicarie]

Hi everyone,

I need help for my project in my Java Programming 1 subject. I really don't have an idea on how to go about with this problem. I have started building the code for the CLASS, but didn't bother to post it, cause everytime after I declare the main method, my mind freezes, that's why I decided to ask for your help. This is the problem anyway...

Consider the sequence of digits from 1 through N (where N = 9) in increasing order 1 2 3 4 5 . . . .N, and insert a (+) for addition or a (-) for subtraction or a () [blank] to run the digits together. Now sum the result and see if you get zero.

Write a program that will find all sequences of length N that produces a ZERO SUM.

Test Case 1

Input
7

Output
1 + 2 - 3 + 4 - 5 - 6 + 7 = 0
1 + 2 - 3 - 4 + 5 + 6 - 7 = 0
1 - 2 + 3 + 4 - 5 + 6 - 7 = 0
1 - 2 - 3 - 4 - 5 + 6 + 7 = 0
1 - 23 + 4 + 5 + 6 + 7 = 0
1 - 23 + 45 + 67 = 0


Test Case 2

Input
8

Output
1 + 2 + 3 + 4 - 5 - 6 - 7 + 8 = 0
1 + 2 + 3 - 4 + 5 - 6 + 7 - 8 = 0
1 + 2 - 3 + 4 + 5 + 6 - 7 - 8 = 0
1 + 2 - 3 - 4 - 5 - 6 + 7 + 8 = 0
1 + 23 - 45 + 6 + 7 + 8 = 0
1 - 2 + 3 - 4 - 5 + 6 - 7 + 8 = 0
1 - 2 - 3 + 4 + 5 - 6 - 7 + 8 = 0
1 - 2 - 3 + 4 - 5 + 6 + 7 - 8 = 0
1 - 23 - 4 + 5 + 6 + 7 + 8 = 0
12 - 34 - 56 + 78 = 0

You may test this program by entering the integer from the keyboard.


Thanks, your help is highly appreciated...

Have you tried to create an algorithm that will calculate the zero-sum?

[ttoboobz]

Have you tried to create an algorithm that will calculate the zero-sum?

I guess not. I did not know that there's an algorithm that does that. I'll just try to research for it here at thescripts or on the internet. but if you have an idea on how to go about that algorithm, i will be delighted if you could teach me...

Thanks for the reply...

[sicarie]

I guess not. I did not know that there's an algorithm that does that. I'll just try to research for it here at thescripts or on the internet. but if you have an idea on how to go about that algorithm, i will be delighted if you could teach me...

Thanks for the reply...

The easiest way (I don't know of an elegant one off the top of my head) would be to brute force it.

Please correct me if I'm wrong - I might be completely off with this, but it seems to me that you give it the number you want the max to be - between 1 and 9 - and it will then print out every combination of one or two digits that add/subtract to 0 when done in sequence, using all the numbers.

So you would start with (for example, given 3),

1+2+3 = 6
1+2-3 = 0
1-2+3 = 4
1-2-3 = -4
12 + 3 = 15
12 - 3 = 9
1 + 23 = 24
1 - 23 = -22
 

In which case you would only print out 1+2-3. Does that sound like a good summarization of your algorithm?

[ttoboobz]

The easiest way (I don't know of an elegant one off the top of my head) would be to brute force it.

Please correct me if I'm wrong - I might be completely off with this, but it seems to me that you give it the number you want the max to be - between 1 and 9 - and it will then print out every combination of one or two digits that add/subtract to 0 when done in sequence, using all the numbers.

So you would start with (for example, given 3),

1+2+3 = 6
1+2-3 = 0
1-2+3 = 4
1-2-3 = -4
12 + 3 = 15
12 - 3 = 9
1 + 23 = 24
1 - 23 = -22
 

In which case you would only print out 1+2-3. Does that sound like a good summarization of your algorithm?

Yes, you got it correct. My problem now is how to insert those plus and minus on my codes. My knowledge on java would only allow me to test your code(your example) one-by-one. It is easier to do it when N is only equal to 3 or 4, but when N is higher, the combinations also rise exponentially, my code would also be very long. . . I was wondering if there's a shorter way to do it....

[sicarie]

Yes, you got it correct. My problem now is how to insert those plus and minus on my codes. My knowledge on java would only allow me to test your code(your example) one-by-one. It is easier to do it when N is only equal to 3 or 4, but when N is higher, the combinations also rise exponentially, my code would also be very long. . . I was wondering if there's a shorter way to do it....

Yeah, like I said, I can't think of any real elegant way to do that - I would suggest brute forcing it at first - also looking at any patterns that might arise when you do them - such as how you calculate when there is a plus sign, or when there is a minus sign.

Anyone else have a good idea for a more elegant algorithm than brute force? (I'm sure there is a way to do it, but it'll take me a bit to figure it out...)

[ttoboobz]

Yeah, like I said, I can't think of any real elegant way to do that - I would suggest brute forcing it at first - also looking at any patterns that might arise when you do them - such as how you calculate when there is a plus sign, or when there is a minus sign.

Anyone else have a good idea for a more elegant algorithm than brute force? (I'm sure there is a way to do it, but it'll take me a bit to figure it out...)

hehe... I might do your suggestion, the not so elegant but doable brute forcing.

Thanks to you, goodluck for me...

[Ganon11]

You could try putting the integers into an array, and the operators into a second array (whose length will be numArray.length - 1). Now, the operator array can be an integer array, with each value being either 0 (addition), 1 (subtraction), or 2(nothing). Then you can iterate through the number array, using the appropriate value from the operator array to evaluate the numbers.

When you finish one execution, you can 'increment' the array to hold the next possibility of operators. You could probably write a method that will give you the next permutation of the operator array.

[ttoboobz]

You could try putting the integers into an array, and the operators into a second array (whose length will be numArray.length - 1). Now, the operator array can be an integer array, with each value being either 0 (addition), 1 (subtraction), or 2(nothing). Then you can iterate through the number array, using the appropriate value from the operator array to evaluate the numbers.

When you finish one execution, you can 'increment' the array to hold the next possibility of operators. You could probably write a method that will give you the next permutation of the operator array.

Yeah, this make a little bit sense to me, thank you guys....