There is a sequence of N random integers, which can contain any integer between 10 and 10 (both of which are inclusive). The task is to find the number of continuous sequences of integers such that their sum is 1 or +1 1 <= n <= 10^6 asked 22 Jun '13, 18:18

Well since you didn't give any memory limit, i'm just going to assume it's 256MB.
Here is a simple pascal code.
Complexity : O(N). Memory used : 41248 kB. http://ideone.com/T9v3Kc  ideone link where you can test the code. answered 23 Jun '13, 12:28
Brilliant answer. Cleverly avoiding the doublecounting and took care of the corner case.
(23 Jun '13, 15:36)

I think the following code can solve the problem. If any explanation is wanted, please ask I shall explain.
Heres the explanation. I have an array of integers of size n where 1<n<10^6 and each element lies in the range 10 to 10. The array element sumupto[i] keeps the sum upto the index i in the given array. Now we also see that the maximum possible value that can ever occur in the array sumupto is 10^7 (ie when n=10^6 and all elements are 10) also, the minimum possible value would be 10^7. Now the array element countsum[i] gives the number of entries with value i in the array sumupto, and so its size must be atleast 2*10^7, and use of offset 10^7 to keep track of the number of negative entires. To find a continuous subsequence, whose sum equals 1 or 1 we simply need to find the number of instances such that abs(sumupto[i]sumupto[j])=1 where 1<i<n and 1<j<n. In doing this we would be counting each such subsequence twice. To do this we simply use the hashtable array countsum, as the number of entries with value = sumupto[i]+1 or value = sumupto[i]1 would give us the answer, but again with each sequence counted twice. Thus we get our answer! answered 22 Jun '13, 22:28
Your logic will fail at an edge case. If there is only one number in the given sequence the number being 1, ur code gives ans=0
(23 Jun '13, 14:50)
What I wanted to point is Let the sequence be from index i to index j  that is a[i] + a[i+1] + ... + a[j] = 1 or 1 then all those sequences where i=0 will not be recognized
(23 Jun '13, 14:53)
1
@sumanth32 yep, you are right, I ignored the cases wherein the sum of sequences is 1 or 1, also if I calculate as I input the numbers I would avoid the error of double counting, which is so nicely presented by c0d3junki3. Correcting it!
(23 Jun '13, 20:42)

Hello, As the use of DP is needed, I say that I also don't know how to solve this problem, but, usually, a recurrence relationship needs to be derived, especially one that can exploit the property of optimal substructure... For instance, let's try to denote: S(i,j) > sum of the elements of the array that start at element i with length j; Also let our array be denoted as Arr. As we want a contiguous subsequence, we can have three cases to consider now: Case 1 S(i,j) = 1 or S(i,j) = 1, case where we add this sequence to our total sequence counter. Case 2 S(i,j) + Arr[i+j+1] > 1 or S(i,j) + Arr[i+j+1] < 1; This case means that, as the next element on our array, (remember we start on element i and have a sequence of length j) A[i+j+1] is not a suitable candidate to form an admissable sequence, so we can possibly restart our sequence counter as S(i+j+1, vl), where vl denotes the variable length that our new subsequence can take. Case 3 A case where S(i,j) + Arr[i+j+1] = 1 or S(i,j) + Arr[i+j+1] = 1, case where we should count this sequence and where we have S(i,j+1) being similar to case 1. Possibly there might be more cases or this formulation might be incorrect, and maybe someone more skilled than me can help you better... I just wrote the formulation that came to my head. This seems like a mix between Kadane's algorithm and the subset sum problem, but I am yet too newbie in DP to help in a more specific way... Best regards, Bruno answered 22 Jun '13, 21:39

link
This answer is marked "community wiki".
answered 22 Jun '13, 22:46
This is a simple Brute Force you are doing. Try to optimize the problem by using DP.
(14 Aug '13, 00:45)
