i want you have a loook over the approach that i have posted just now you will love it and it is quite intutive too. because everyone does nt know about pegion hole principle.
Here’s an example: Let’s say our multi-set contains the elements {1,2,2,3,4,4}. Now lets calculate the cumulative frequencies, i.e bi’s. b0 = 0, b1 = 1, b2 = 3, b3 = 5, b4 = 8, b5 = 12, b6 = 16. Now take the remainders of each of these with 6, which gives {0,1,3,5,2,0,4}. Here we have b0%6 == b5%6, so (b5-b0)%6==0 => b5-b0 is divisible by 6 (or N in this case). what is b5-b0, it’s nothing but
{1+2+2+3+4}, which is the sum of contiguous elements of the multiset. Why did this work? There were 7 bi’s (b0-b6), but bi%6 can take only values 0-5 (6 values), so atleast 2 bi%6’s must be equal.
11 Likes
really pigeonhole principle is so amazing
i guess the explanation provided is not that clear
see there are n different prefixes so if we apply modulo n to each of them then we will get values from 0 to n-1. if any prefix gives zero it is directly the answer. now considering the prefix dont give 0 then since there are n prefixes and n-1 values of remainder(1to n-1)
according to pigeonhole principle atleast 2 of the prefixes will have same mod values.
then the answer is the difference of those prefixes as explained by the author.
2 Likes
Even If I knew Pigeonhole principle I was not able to approach the answer 