## Monday, November 14, 2016

### Smallest subarray whose sum is multiple of array size - GeeksforGeeks

Smallest subarray whose sum is multiple of array size - GeeksforGeeks
Given an array of size N, we need to find smallest sized subarray whose sum is divisible by array size N.

We can solve this problem considering below facts,
```Let S[i] denotes sum of first i elements i.e.
S[i] = a[1] + a[2] .. + a[i]
Now subarray arr(i, i + x) has sum multiple of N then,
(arr(i] + arr[i+1] + .... + arr[i + x])) % N = 0
(S[i+x] – S[i] ) % N  = 0
S[i] % N = S[i + x] % N ```
We need to find the minimum value of x for which the above condition holds. This can be implemented in single iteration with O(N) time-complexity using another array modIdx of size N. Array modIdx is initialized with all elements as -1. modIdx[k] is to be updated with i in each iteration, where k = sum % N.
Now in each iteration we need to update modIdx[k] according to the value of sum % N.

We need to check two things,
If at any instant k = 0 and it is the first time we are updating modIdx[0] (i.e. modIdx[0] was -1)
Then we assign x to i + 1, because (i + 1) will be the length of subarray whose sum is multiple of N
In other case whenever we get a mod value, if this index is not -1, that means it is updated by some other sum value, whose index is stored at that index, we update x with this difference value, i.e. by i – modIdx[k].
After each above operation we update the minimum value of length and corresponding starting index and end index for the subarray. Finally, this gives the solution to our problem.
`void` `printSubarrayMultipleOfN(``int` `arr[], ``int` `N)`
`{`
`    ``// A direct index table to see if sum % N`
`    ``// has appeared before or not.   `
`    ``int` `modIdx[N]; `

`    ``//  initialize all mod index with -1`
`    ``for` `(``int` `i = 0; i < N; i++)`
`        ``modIdx[i] = -1;`

`    ``// initializing minLen and curLen with larger`
`    ``// values`
`    ``int` `minLen = N + 1;`
`    ``int` `curLen = N + 1;`

`    ``// To store sum of array elements`
`    ``int` `sum = 0;`

`    ``//  looping for each value of array`
`    ``int` `l, r;`
`    ``for` `(``int` `i = 0; i < N; i++)`
`    ``{`
`        ``sum += arr[i];`
`        ``sum %= N;`

`        ``// If this is the first time we have`
`        ``// got mod value as 0, then S(0, i) % N`
`        ``// == 0`
`        ``if` `(modIdx[sum] == -1 && sum == 0)`
`            ``curLen = i + 1;`

`        ``// If we have reached this mod before then`
`        ``// length of subarray will be i - previous_position`
`        ``if` `(modIdx[sum] != -1)`
`            ``curLen = i - modIdx[sum];`

`        ``//  choose minimum length os subarray till now`
`        ``if` `(curLen < minLen)`
`        ``{`
`            ``minLen = curLen;`

`            ``//  update left and right indices of subarray`
`            ``l = modIdx[sum] + 1;`
`            ``r = i;`
`        ``}`
`        ``modIdx[sum] = i;`
`    ``}`

`    ``//  print subarray`
`    ``for` `(``int` `i = l; i <= r; i++)`
`        ``cout << arr[i] << ``" "``;`
`    ``cout << endl;`
`}`