In the divisible arrray problem?

#1

in the divisible arrray problem
why are we taking extra 0 in the prefix array at the starting?

#2

also explain where pigeon hole principle is used ?

#3

this is used to apply pigeon hole principle

so that we have n+1 peigeons and only n holes

now we have n+1 elements in prefix array
but the mod can be only from 0 to n-1 so total n distinct nos at max

you can see now we have n+1 peigons and n holes
in this way we are applying peigon hole principle to this qustion

if you have more doubts regarding this feel free to ask
i hope this helps
if yes hit a like and don’t forgot to mark doubt as resolved :grinning: