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
Read full article from Longest Subarray with Sum Divisible by K | Algorithms Notes
No comments:
Post a Comment