Oggy, Cockroaches and Puzzle
What more could Oggy, the cat can do to stop the three troublesome cockroaches Joey, Dee Dee and Marky who have made his life miserable?
Sickened by their mischiefs, Oggy decided to go on an agreement that would help settle the dispute between Oggy and the cockroaches once for all.
According to the agreement, Oggy announced that if the cockroaches try to answer a puzzle shooted by him, then Oggy would accept the cockroaches as his Boss and would be at their service forever.
If the cockroaches fail to answer, then luck is still favourable on Oggy and the cockroaches should leave his house permanently. The puzzle Oggy gave the cockroaches to answer is:
Given N numbers which are either positive or negative, the cockroaches has to find the number of continuous sequence of numbers such that their sum is zero.
For example if the sequence is- 5, 2, -2, 5, -5, 9
There are 3 such sequences 2, -2 5, -5 2, -2, 5, -5
Since this is a golden opportunity for the cockroaches they can't afford to lose.
So they turn to you for help. Don't let them down.
Input Format The first line of the input contains an integer n, which corresponds to the number of elements in a the input array.
The next line contains n space-separated integers a i (1<=i<= n).
Output Format The number of such sequences whose sum if zero. Refer sample input and output for formatting specifications.
Sample Input 1: 4 0 1 -1 0
Sample Output 1: 6
Sample Input 2: 6 5 2 -2 5 -5 9
Sample Output 2: 3
What more could Oggy, the cat can do to stop the three troublesome cockroaches Joey, Dee Dee and Marky who have made his life miserable?
Sickened by their mischiefs, Oggy decided to go on an agreement that would help settle the dispute between Oggy and the cockroaches once for all.
According to the agreement, Oggy announced that if the cockroaches try to answer a puzzle shooted by him, then Oggy would accept the cockroaches as his Boss and would be at their service forever.
If the cockroaches fail to answer, then luck is still favourable on Oggy and the cockroaches should leave his house permanently. The puzzle Oggy gave the cockroaches to answer is:
Given N numbers which are either positive or negative, the cockroaches has to find the number of continuous sequence of numbers such that their sum is zero.
For example if the sequence is- 5, 2, -2, 5, -5, 9
There are 3 such sequences 2, -2 5, -5 2, -2, 5, -5
Since this is a golden opportunity for the cockroaches they can't afford to lose.
So they turn to you for help. Don't let them down.
Input Format The first line of the input contains an integer n, which corresponds to the number of elements in a the input array.
The next line contains n space-separated integers a i (1<=i<= n).
Output Format The number of such sequences whose sum if zero. Refer sample input and output for formatting specifications.
Sample Input 1: 4 0 1 -1 0
Sample Output 1: 6
Sample Input 2: 6 5 2 -2 5 -5 9
Sample Output 2: 3
No comments: