Please Visit: http://ift.tt/1ajReyV
from Public RSS-Feed of Jeffery yuan. Created with the PIXELMECHANICS 'GPlusRSS-Webtool' at http://gplusrss.com http://ift.tt/1r2htHT
via LifeLong Community
Longest Subarray with Sum Divisible by K | Algorithms Notes
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).
http://ift.tt/1r2htHL
http://ift.tt/XZbCqb
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).
http://ift.tt/1r2htHL
http://ift.tt/XZbCqb
from Public RSS-Feed of Jeffery yuan. Created with the PIXELMECHANICS 'GPlusRSS-Webtool' at http://gplusrss.com http://ift.tt/1r2htHT
via LifeLong Community
No comments:
Post a Comment