Why are we taking six buckets in the csum array?

#1

after taking the cumulative sum, why we are taking siz buckets in array even if only five are needed?. This goes out of logic for me!!! please clarify?

#2

@subham221 hey we have taken 6 elements in cumm sum array as first element of cumm sum array is 0 and with the help of that element we fill rest array by taking cs[i-1]+a[i],also now how to take bucket depend on n,suppose n is 5 so if we do mod of any no with n than ans will be from 0 to n-1 or here 5-1 that is 4 so to store their frequencies we have to take that much buckets,hope now it become clear.

#3

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.

#4

But we can find the cumulative sum using five buckets as well…as we found the cumulative sum in the case of maximum sum subarray!!!. In that problem, we used cum sum buckets equal to the number of buckets in the given array. Then why we are taking zero in the beginning of this case. & if we are taking six buckets in this case which is one more than the given array elements then why we didn’t accounted zero as the first element of cumulative sum subarray in the case of maximum sum subarray problem?

#5

It is making a little bit confusing both the scenarios?. if we didn’t take six buckets then why we are taking one more bucket in this case?

#6

hi @subham221
we have make csum array of size n+1 to apply peigon hole principle
suppose
arr= 1 2 3 4 5
n=5
csum= 0 1 3 6 10 15
now taking mod with csum we get n+1 numbers
but taking mod with n we can get only only n different nos
so atleast one num should repeat

so i hope it is clear now
it is just to apply peigon hole principle

#7

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.