Given an integer array A of length n and an integer K, design an O(n lg n) algorithm to find the longest subarray, subject to the sum of the subarray is divisible by K.
Solution:
Let S[i] be the sum of A[1..i], R[i] be S[i] % K. The sum of subarray A[i..j] = S[j] – S[i] is divisible by K if, and only if, R[i] = R[j]. Hence, we can sort R[i] and find the largest i – j, such that R[i] = R[j]. The total complexity is O(n lg n).
We also can count the number of subarrays whose sum is divisible by K. Let Q[i] be the number of indicies with R[j] = i. The sum of (Q[i] * Q[i-1])/2 over all i is the number of subarrays whose sum is divisible by K. The total complexity is O(n lg n).
We also can find the maximum subarray sum subject to the sum of the subarray is divisible by K. For an index j, we want to find i < j, such that R[i] = R[j] with minimum sum of S[i]. This can be done by using a self-balancing binary search tree. The total complexity is O(n lg n).
解法：
令S[i]為A[1..i]的總和，R[i]為S[i]% K。子陣列A[i..j]可被K整除若且唯若R[i] = R[j]。因此我們可以把R[i]排序，然後找出最大的i – j使得R[i] = R[j]。時間複雜度為O(n lg n)。
我們也可以計算陣列和可被K整除的子陣列個數。令Q[i]表示R[j] = i的索引個數。(Q[i] * Q[i-1])/2對所有i的總和即為所求。時間複雜度為O(n lg n)。
我們也可以找出陣列和可被K整除的子陣列中，陣列和最大的子陣列。對一索引j而言，我們要找出一索引i < j，使得R[i] = R[j]且S[i]最小。利用self-balancing binary search tree即可。時間複雜度為O(n lg n)。
Reference: Stackoverflow, Stackoverflow, Stackoverflow
Algorithms Notes 
This can be solved in O(n) time and O(n) space.
After getting R[] array, we just need to find R[i]=R[j] and (j-i) should be max.
After that we can use similar logic of this post: http://www.geeksforgeeks.org/largest-subarray-with-equal-number-of-0s-and-1s/
NOTE: In above mentioned link, it creates an array sumLeft[] which is exactly the R[] array of this question. Rest code flows as it is. Just focus a bit and you will get the solution.
Nice. In order to find maximum (j – i) subject to R[i] = R[j], the method used on geeksforgeeks needs a hashtable. In their problem, since the hash table can be implemented by an array of length O(n), constant running time per operation in the worst case is guaranteed. But in this problem, can you implement a hash table that guarantees constant running time per operation in the worst case?
Yeah we can. The R[] array will have range 0 to K-1. If K<<n(i.e num of inputs), we can directly use array as hashtable Aux[]. For every R[ j ], we just have to store the first found index of R[j] (i.e j here) at Aux[R[i]]. So it 'll be something like this: Aux[R[j]] = j. When R[j] comes again then compare it's distance with first found index using Aux[] array. You 'll get the max length all the time. Here every operation is constant as we are not iterating on Aux[] array to find any value.
Great, your algorithm is correct, but you are assuming K<<n. Without this assumption, your algorithm is O(K), which is exponential, in the worst case.
It’s O(k) space, not O(k) time. It’s still O(n) time. If k>>n then we can use hashtable which ‘ll take O(n) space only.
Thanks for your comment. Space complexity is a lower bound of time complexity, since initializing an array of length K takes O(K) time. Hence, Θ(K) space implies Ω(K) running time. In practice, there are some tricks that can avoid O(K) initialization, but I don’t want to use these tricks in this problem. Furthermore, when K = Ω(n), using a hash table does not guarantee O(1) time per operation in worst case.
Yeah. That’s correct.