# DIVSUBS - Editorial

**URL:** <https://discuss.codechef.com/t/divsubs-editorial/5534>\
**Category:** general\
**Tags:** ltime12, pigeonhole, simple\
**Created:** [May 25, 2014, 2:00pm UTC](https://discuss.codechef.com/t/divsubs-editorial/5534 "2014-05-25T14:00:30Z")\
**Posts on this page:** 5\
**Page:** 2

<div class="post-metadata">

**Author:** ![ma5termind](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@ma5termind](https://discuss.codechef.com/u/ma5termind)\
**Post date:** [May 26, 2014, 11:24am UTC](https://discuss.codechef.com/t/divsubs-editorial/5534/21 "2014-05-26T11:24:56Z")

</div>

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.😃

---

<div class="post-metadata">

**Author:** ![midhul](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@midhul](https://discuss.codechef.com/u/midhul)\
**Post date:** [May 28, 2014, 10:14am UTC](https://discuss.codechef.com/t/divsubs-editorial/5534/22 "2014-05-28T10:14:17Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![akshatbhutra](https://discuss.codechef.com/user_avatar/discuss.codechef.com/akshatbhutra/32/208155_2.png) [@akshatbhutra](https://discuss.codechef.com/u/akshatbhutra)\
**Post date:** [August 15, 2019, 2:45pm UTC](https://discuss.codechef.com/t/divsubs-editorial/5534/23 "2019-08-15T14:45:00Z")

</div>

really pigeonhole principle is so amazing

---

<div class="post-metadata">

**Author:** ![ujjwal\_p](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@ujjwal\_p](https://discuss.codechef.com/u/ujjwal_p)\
**Post date:** [June 18, 2020, 10:45am UTC](https://discuss.codechef.com/t/divsubs-editorial/5534/24 "2020-06-18T10:45:34Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![rg\_rupeee](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rg_rupeee/32/15967_2.png) [@rg\_rupeee](https://discuss.codechef.com/u/rg_rupeee)\
**Post date:** [May 14, 2021, 7:26pm UTC](https://discuss.codechef.com/t/divsubs-editorial/5534/25 "2021-05-14T19:26:56Z")

</div>

Even If I knew Pigeonhole principle I was not able to approach the answer 😥

[Previous page](https://discuss.codechef.com/t/divsubs-editorial/5534.md?page=1)