phantom11's blog

Circular array cumulative sum
By phantom11, 13 years ago, In English
Hello coders,
I was preparing for the regional finals and came across a question which asks to find the number of ways in which a circular array can be divided into two parts such that sum of elements in both parts is equal.
So this has to do something with cumulative sum in an array.One of the participants wrote the following code(presenting the snippet only)

total=sum of all elements/2
if total%2==1 return 0
for(i=0 to n-1)
{
sum+=a[i]
ans+=cnt[sum]
cnt[sum+total]++
}
print ans

I want to know what is the logic behind this...Also if some one has links/or has some more questions involving cumulative sum of circular arrays please post it(I guess this is author's favourite topic)..Thanks in advance
  • Vote: I like it
  • -12
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
........it's like first u can calculate sum upto every i'th element...& as we know if split the array from (i,j)postion then 
                                         s[j]-s[i]=total/2 i.e s[j]=s[i]+total/2......so  wn we pass from every ith element we are actually  incrementing the value for the j'th element (if it exists)..& wn we will pass through j we will increment ans....
           ............i hope this is enough...  
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks....It clears my doubts
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    i don't understand these things thoroughly . would you mind explain it more.
    thanks.
    → Reply