Divisible subarray

[mzk1994 (moody kloob)]

sir why do you initialize pre[0] as 1?

[aman212yadav (Aman Yadav)]

hello @mzk1994

empty subarray will have zero sum and thats why we are initialising pre[0] with 1.

refer this discussion for clarity->

DIVISIBLE SUBARRAYS

consider this case-> n=3 1 2 3 subarray whose mod is 0-> (1,2) (3), (1,2,3) right? but the prefix formula we are using will count only 2 subarrays. i.e it will count only (1,2) , (3) so to avoid this we are initialsing it with 1.

if that wont make sense then iniitialise pre[0] with 0.

and use pre[0] * (pre[0]-1)/2 + pre[0] formula for contribution of 0.

adding pre[0] because these are the times when prefix is itself 0,and it is not counted in above formula (pre[0]*(pre[0]-1)/2)

[aman212yadav (Aman Yadav)]

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.