bc_mc_bsdk_mkc's blog

PigeonHole principle
By bc_mc_bsdk_mkc, history, 4 years ago, In English

Hey everyone I am stuck in this problem Find a non empty subset in an array of N integers such that sum of elements of subset is divisible by N It's also available on gfg link... but explanation is not quiet clear !! it will be really helpful if some-one explains approach to me.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

If you consider prefix sums of size 1, 2, 3... N, there are N different prefix sums. If all of the prefix sums are different mod N, then you know one of them is divisible by N and the solution is that entire prefix sum(because there are N residues mod N and N prefix sums). Otherwise, if the prefix sums are not all different mod N, then that means that two of them are congruent, so the set you want is just the larger prefix sum minus the smaller one of the same residue mod N.

→ Reply