CODEWITHSUNDEEP
dynamic-programming
user11910577
user11910577

Reputation:

Check whether a subset with sum divisible by m exists

Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.

The solution on geeksforgeeks states that-

  1. If n > m there will always be a subset with sum divisible by m (which is easy to prove with pigeonhole principle). So we need to handle only cases of n <= m.

Can somebody please explain what this case means and what is its relation to pigeonhole principle? Also how is this case different from n <= m?

Upvotes: 1

Views: 2265

Answers (2)

Isdj
Isdj

Reputation: 1856

Let us create a new set of numbers (i.e. a[ ] array) by doing prefix sum of given values (i.e. value[ ] array).

a[0] = value[0]
a[1] = value[0] + value[1]
a[n] = value[0] + value[1] + .... + value[n]

Now we have n new numbers. If any of them are divisible by m we are done.

If we divide the a[ ] array elements with m, we can get remainders in range of [1, m - 1].
But, we have a total of n values.
So, there exist two numbers 0<=i,j<=n in a such that a[i] mod(m) == a[j] mod(m).
Due to the above statement, we can say that a[i] - a[j] is divisible by m.

Now, let's consider i > j. We also know that, a[i] = value[i] + value[i - 1] + ... + value[0] and a[j] = value[j] + value[j - 1] + ... + value[0].

So, a[i] - a[j] = value[i] + value[i - 1] + ... + value[i - j + 1] is also divisible by m.

Upvotes: 1

h3yduck
h3yduck

Reputation: 1809

Making this a bit more verbose of this:

Label the numbers a1, a2, ... an in any order. Now consider the sums:

b1=a1
b2=a1+a2
b3=a1+a2+a3
...
bn=a1+a2+...+an

These are either all unique numbers or one of the as are 0 (which is divisible by m).

  1. Now if any of the bs are divisible by m we are done.

  2. Otherwise:

The remainders of some non-divisible number/m can be in the range of 1...(m-1). So there are m-1 numbers of possible remainders`.

Since numbers b1...bn weren't divisible by m they must have remainders in the range of 1...(m-1). So you must pair n numbers of bs (pigeons) with m-1 remainders (pigeonholes).

We have more pigeons than pigeonholes => there must be at least two pigeons in the same pigeonhole.

That means: there must be at least two bs with the same remainder: call them bi, bj (i<j). Since all of our bs are unique and bi % m == bj % m (the remainders of bi/m and bj/m are the same) => bi - bj = x * m (where x is a positive integer). Therefore bi - bj is divisible by m and bi - bj = ai+1 + ... + aj. Therefore ai+1 + ... + aj is divisible by m which is exactly what we wanted to proof.

Upvotes: 3

Related Questions