Table of 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){
    int N = nums.size();
    map<int, vector<int>> indexInfo;

    index[0].push_back(-1);

    // the remainder at current index
    int cur_remainder = 0;
    int maxLen = 0;

    for (int i = 0; i < N; i++) {
        cur_remainder = (cur_remainder + nums[i]) % K;

        if (indexInfo[cur_remainder].size() != 0){
            maxLen = max(maxLen, i - indexInfo[cur_remainder].front());
        }

        indexInfo[cur_remainder].push_back(i);
    }

    return maxLen;
}

Note that the line index[0].push_back(-1); is needed. Otherwise, for $A = [3]$ and $k=3$ , we can not the right answer.

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.