Pigeon Hall Principal:-
It says that for a given Array of numbers (A[i]>=1) , if you choose any interval
[ s , e ] (where "s=starting index" and "e=end index" ) then it is always possible to find a subArray or subSet of [ s, e] such that
"sum of numbers of that subArray or subSet is always divisible by ( e - s + 1)".
for example:- Consider A=[1 , 3 , 6 , 2 , 7 , 8] and [ s , e]=[1,4]
Here, (e-s+1)=4 and A( [ s , e] )=[3 , 6 ,2 , 7] , consider the subArray [ 6 , 2 ] whose sum is 8 , which is divisible by 4. you can take any interval and verify it ,
"it is always possible to find such subArray ( it may be whole interval itself )".
link to related question: https://www.hackerrank.com/contests/recode-4/challenges/watari-queries ,
where one can use this concept.
It says that for a given Array of numbers (A[i]>=1) , if you choose any interval
[ s , e ] (where "s=starting index" and "e=end index" ) then it is always possible to find a subArray or subSet of [ s, e] such that
"sum of numbers of that subArray or subSet is always divisible by ( e - s + 1)".
for example:- Consider A=[1 , 3 , 6 , 2 , 7 , 8] and [ s , e]=[1,4]
Here, (e-s+1)=4 and A( [ s , e] )=[3 , 6 ,2 , 7] , consider the subArray [ 6 , 2 ] whose sum is 8 , which is divisible by 4. you can take any interval and verify it ,
"it is always possible to find such subArray ( it may be whole interval itself )".
link to related question: https://www.hackerrank.com/contests/recode-4/challenges/watari-queries ,
where one can use this concept.
