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