Блог пользователя phantom11

Автор phantom11, 13 лет назад, По-английски
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
  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
........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...