**Problem**

Given an array A, a subset of S (i_{0}, i_{1}, i_{2}… i_{k}) of A such that Sum(S) mod n = 0. This is the 0 mod n subset problem. Find this subset.

**Solution**

The general case of 0 mod k is NP complete however 0 mod n can be computed efficiently O(n) time and O(n) space. Also in the case of n, there is always guaranteed to be a solution as seen below.

First create the array mod_till_k such that

mod_till_k[i] = Sum(A[0] .. A[i]) mod n

This is implemented below:

mod_till_k :: [Integer] -> [Integer]
mod_till_k xs = mod_till_k' 0 xs
where
n = length xs
mod_till_k' :: Integer -> [Integer] -> [Integer]
mod_till_k' _ [] = []
mod_till_k' prev (x:xs) = curr : (mod_till_k' curr xs)
where curr = mod (x + prev) (toInteger n)

Now if mod_till_k[x] == 0, then the subset [0,x] is a solution.

If there no x such that mod_till_k[x] == 0, then there WILL exist some a < b such that mod_till_k[a] == mod_till_k[b]. In this case the solution is [a + 1,b]

This search can done linearly with.

zero_mod_n_subset :: [Integer] -> (Integer, Integer)
zero_mod_n_subset xs = zero_mod_n_subset' 0 index_table (mod_till_k xs)
where
n = length xs
index_table = array (0, toInteger (n - 1)) [(toInteger i, -1) | i <- [0..n - 1]]
zero_mod_n_subset' i index_table (x:xs)
| x == 0 = (0,i)
| index_table!x /= -1 = (index_table!x,i)
| otherwise = zero_mod_n_subset' (i + 1) (index_table // [(toInteger x,toInteger i)]) xs

Here index_table, which is initialised to -1, keeps track of previous positions where a particular mod was last seen.

### Like this:

Like Loading...

*Related*

[…] EPI 6.5 – Subset summing to 0 mod n […]