Longest Subarray Sum Divisible by K
JavaView on GFG
Problem Overview
A contiguous sum is divisible by k exactly when two prefix sums leave the same remainder modulo k.
Intuition
A contiguous sum is divisible by k exactly when two prefix sums leave the same remainder modulo k. To make the segment as long as possible, remember the earliest index where each remainder appeared. Meeting that remainder again at index i gives a candidate length of i minus that earlier index. Remainder 0 is seeded at index minus 1 so a prefix that is itself divisible by k is counted from the start.
Algorithm
- 1Allocate an array first of length k filled with a sentinel meaning unseen, and set first[0] to -1.
- 2Scan the array while keeping a running prefix sum.
- 3Normalize the remainder as ((sum % k) + k) % k so negatives land in 0 through k minus 1.
- 4If that remainder was seen before, update the answer with i minus first[rem]; otherwise store i as the first occurrence.
- 5Return the best length found.
Example Walkthrough
Input: arr = [2, 7, 6, 1, 4, 5], k = 3
- 1. Prefix remainders include a repeat of remainder 0 between early and later indices that spans length 4.
- 2. That window is 7, 6, 1, 4 whose sum 18 is divisible by 3.
- 3. No longer valid window exists, so the answer is 4.
Output: 4
Common Pitfalls
- • Store only the first index of each remainder. Overwriting with a later index shortens every later candidate.
- • Normalize negative mods. In Java sum % k can be negative when the prefix is negative.
- • Use a 64 bit prefix sum. Large values can overflow a 32 bit accumulator before the mod.
- • An array of size k beats a hash map under the usual constraint that k is at most about 1e6.
Longest Subarray Sum Divisible by K.java
Java
// Approach: A subarray sum is divisible by k iff two prefix sums share the
// same remainder mod k. Store the earliest index of each remainder; the
// farthest matching pair for that rem is the longest valid subarray. An
// array of size k replaces a hash map under the usual k bound.
// Complexity: O(n) time, O(k) extra space.
class Solution {
public int longestSubarrayDivK(int[] arr, int k) {
int[] first = new int[k];
java.util.Arrays.fill(first, -2);
first[0] = -1;
long sum = 0;
int maxLen = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
int rem = (int) ((sum % k + k) % k);
if (first[rem] != -2)
maxLen = Math.max(maxLen, i - first[rem]);
else
first[rem] = i;
}
return maxLen;
}
}Was this solution helpful?