# Find Longest Subarray Whose Sum Is Divisible by K

## Contents

The problem is as follows:

Given an array $A$ of length $N$, $A[i] \ge 0$ ( $0 \le i \le N-1$) , and a number $K$. Find the longest subarray whose sum is divisible by $K$, if there are no such subarray, return 0;

The idea is to traverse the array and record the result of cumulative sum modulo $K$ and its corresponding index. If for index $i, j$, the remainder is the same, then the subarray between $i, j$ must be a valid subarray (i.e., its sum is divisible by $K$). In order to find the longest subarray, we can keep a list of index corresponding to each remainder (there are $K$ remainders, $0, 1, 2, …, K-1$). During the traversing process, we can also easily find the longest subarray (index list of each remainder is stored in ascending order).

Below is the implementation of the above idea:

```
int findLongestSubarray(vector<int>& nums){
map<int, vector<int>> indexInfo;
indexInfo[0].push_back(0);
int cur = 0;
int maxLen = 0;
for (int i = 0; i != N; i++) {
cur = (cur + nums[i]) % K;
if (indexInfo[cur].size() != 0){
maxLen = max(maxLen, i - indexInfo[cur].front());
}
indexInfo[cur].push_back(i);
}
return maxLen;
}
```

Time complexity, traversing the array and finding the maxLen during the process takes $O(n)$ time. Space complexity is apparently $O(n)$.

P.S. Thanks to Scott for pointing out that there is no need to sort the list corresponding to each remainder, because they are already in sorted order.