Why we are taking the size of the cumulative sum array (n+1)

#1

why we are taking the size of the cumulative sum array (n+1).

#2

hello @rick711c

no reason behind that , u can take n size arrray as well

#3

but then there will be 5 numbers and 5 places . so we can not apply pigeon hole

#4

…

why ? our prefix some is unbounded it can take any value and since we are taking mod with n the result will fall in [0…n-1] and we can use pigeon on this

#5

i did not understand. if we not take 0 then our cumulative sum array will be 1,4,6,12,16 and after taking mod with 5 , the array will be like 1,4,1,2,1 . so there is 5 elements . taking mod of any number with 5 we can get 0,1,2,3,4 total 5 numbers

#6

later on the video , he use the 0 as a product of null sub arrays . i did not understand that

#7

…

see here 1 is getting repeated…

thats because the cumulative value may exceed n and taking its mod with n will make limited to range [0…n-1]

so its obvios that some value will get repeated.

like here 1 is repeated…

dont just go by pigeon hole definition try to understand its meaning

#8

…

an empty subarray has 0 sum so thats why count is 1 initially

#9

i can understand that we can solve this problem without taking the 0. but it’s feels like we only take the 0 just to not break the pigeon hole rule . i just want to know that is there any valid explanation of taking the 0?

#10

i think that taking of the 0 in the cumulative sum array will make a difference . because after taking the 0, we have 6 elements in the CS array , so we get 6 elements after taking mod - 0,1,4,1,2,1 …as there is 6 elements , now we can say according to the pigeon hole rule there must be a sub array such that sum of elements of that array is divisible by 5 . but if we do not take 0 then there will be 5 elements , so there is no guarantee that we get such subarray

#11

…

its nothig like that.
also we are saying its pigeonn hole not becuase it will have n elements.
its becuse the prefix sum%n will fall in range [0…n-1] so some holes may get filled more than once.
0 is not to make n elements,intead its there because emoty subarry sum is 0.

do one thing just ignore the word pigeon hole and rewtch the video u can get the logic without that as welll.

#12

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.