Find Longest Subarray with Sum Divisible by K

Title: Find Longest Subarray with Sum Divisible by K

In this guide, you’ll learn how to find the longest subarray whose sum is divisible by a given number k. This is a classic prefix sum interview problem that shows up frequently in array and coding-round interviews.

We’ll walk through the brute force intuition, build an efficient O(n) solution using prefix sums and a HashMap, then trace it step by step so you can defend the approach confidently in an interview.

Understanding the Problem

Given an integer array arr and an integer k, you need to find the length of the longest contiguous subarray whose sum is exactly divisible by k, meaning sum % k == 0. A subarray is a contiguous slice of the original array, not an arbitrary subset.

For example, with arr = {2, 7, 6, 1, 4, 5} and k = 3, the subarray {7, 6, 1, 4} sums to 18, which is divisible by 3, and no longer contiguous slice also satisfies the condition. The expected output is 4.

The naive approach checks every subarray’s sum directly, which costs O(n^2) time for an array of length n. The insight that gets us to O(n) is that the sum of any subarray can be expressed as the difference of two prefix sums.

Approach / Algorithm Steps

The algorithm relies on one property of modular arithmetic: if two prefix sums leave the same remainder when divided by k, the subarray between them sums to a multiple of k. Here’s the step-by-step approach.

1. Compute a running prefixSum as you iterate through arr from left to right.
2. At each index i, compute the remainder as ((prefixSum % k) + k) % k so it is always non-negative, even when prefixSum is negative.
3. Store the first index at which each remainder is seen in a HashMap of remainder to index, seeded with (0, -1) so a prefix that is already divisible by k from the start is counted correctly.
4. If the current remainder has already been seen, the subarray between the stored index and the current index i sums to a multiple of k; update maxLength if this subarray is longer than the best one found so far.
5. If the remainder has not been seen before, record the current index as its first occurrence; never overwrite an existing entry, since a later occurrence would only shorten the resulting subarray.
6. After the loop finishes, maxLength holds the length of the longest subarray whose sum is divisible by k.

Java Program

Here’s the complete, compilable Java program implementing the algorithm above.

import java.util.HashMap;
import java.util.Map;

public class LongestSubarrayDivisibleByK {

    public static int longestSubarrayDivisibleByK(int[] arr, int k) {
        Map<Integer, Integer> firstIndexOfRemainder = new HashMap<>();
        firstIndexOfRemainder.put(0, -1);

        int prefixSum = 0;
        int maxLength = 0;

        for (int i = 0; i < arr.length; i++) {
            prefixSum += arr[i];
            int remainder = ((prefixSum % k) + k) % k;

            if (firstIndexOfRemainder.containsKey(remainder)) {
                int length = i - firstIndexOfRemainder.get(remainder);
                maxLength = Math.max(maxLength, length);
            } else {
                firstIndexOfRemainder.put(remainder, i);
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] arr = {2, 7, 6, 1, 4, 5};
        int k = 3;

        int result = longestSubarrayDivisibleByK(arr, k);
        System.out.println("Longest subarray length divisible by " + k + " is: " + result);
    }
}

Explanation of the Program

The method longestSubarrayDivisibleByK makes a single pass over arr while maintaining a running prefixSum and a map from remainder to its first index.

The line firstIndexOfRemainder.put(0, -1) handles the case where a prefix starting at index 0 is already divisible by k; without it, that subarray would be missed because there is no earlier index to subtract from.

Normalizing with ((prefixSum % k) + k) % k matters because Java’s % operator can return a negative value when prefixSum is negative. Without normalization, -7 % 3 and 2 % 3 would be treated as different remainders even though they belong to the same residue class.

Whenever a remainder repeats, i - firstIndexOfRemainder.get(remainder) gives the exact length of the subarray between the two prefix sums, because the elements between those indices are the ones that cancel out under subtraction.

Step-by-Step Trace

Trace the algorithm on arr = {-7, 2, 5, 1, -2, 6} with k = 3. The final answer is a longest subarray length of 5.

At the end of iteration i, maxLength holds the length of the longest subarray ending at or before index i whose sum is divisible by k.

Examples

The following examples show the method handling a longer array and an array with no qualifying subarray at all.

Example 1: A Longer Array With a Partial Match

With arr = {3, 1, 4, 1, 5, 9, 2, 6} and k = 5, the longest subarray divisible by 5 excludes only the last element.

int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
int k = 5;
int result = longestSubarrayDivisibleByK(arr, k);
System.out.println(result);
// Output: 7
// The subarray {3, 1, 4, 1, 5, 9, 2} sums to 25, which is divisible by 5.

Example 2: No Subarray Divisible by K

With arr = {1, 2, 3} and k = 10, none of the prefix sums repeat a remainder, so the method correctly reports that no subarray qualifies.

int[] arr = {1, 2, 3};
int k = 10;
int result = longestSubarrayDivisibleByK(arr, k);
System.out.println(result);
// Output: 0
// No non-empty subarray sums to a multiple of 10, so the method returns 0.

Common Mistakes to Avoid

These are the mistakes candidates most often make when implementing this algorithm under interview pressure.

• Off-by-one in the length calculation. Computing the length as i - firstIndexOfRemainder.get(remainder) + 1 overcounts by one element, since the subarray actually starts right after the stored index, not at it. Drop the + 1 and use i - firstIndexOfRemainder.get(remainder) directly.
• Forgetting to seed remainder 0 at index -1. Without put(0, -1), a prefix that is already divisible by k starting from index 0 is silently skipped, undercounting the true longest subarray. Initialize the map with that entry before the loop starts.
• Overwriting the first occurrence of a remainder. Updating the map every time a remainder is seen keeps only the most recent index, which shrinks the resulting subarray length instead of maximizing it. Only insert an index the first time its remainder appears, using containsKey as a guard.
• Not normalizing negative remainders. Java’s % can return a negative result for a negative prefixSum, so -7 % 3 and 2 % 3 end up as different map keys even though they represent the same remainder. Always wrap the modulo in ((prefixSum % k) + k) % k.
• Confusing a 0 result with ‘no answer found’. Returning 0 for both ‘no subarray qualifies’ and ‘the longest qualifying subarray has length 0’ is ambiguous to a caller. Document the 0 return value explicitly, or return -1 if the API needs an unambiguous ‘not found’ signal.

Edge Cases to Test

Before calling the solution done, walk through these boundary inputs out loud; interviewers specifically look for this habit.

• Empty array
• Single-element array
• Array containing negative numbers
• No subarray with sum divisible by k
• Entire array sum divisible by k
• k equal to 1
• Array containing zeros
• k larger than the sum of all elements

Additional Considerations

The algorithm runs in O(n) time since it makes a single pass over arr, with each HashMap lookup and insertion costing O(1) on average.

Space usage is O(min(n, k)) because there are only k possible remainders, so the map never grows past k entries no matter how large arr is.

This is a significant improvement over the brute force O(n^2) approach that checks every subarray sum directly, and it generalizes the equal zeros-and-ones subarray trick to an arbitrary modulus instead of just parity.

Interview Follow-up Questions

Once you’ve nailed the base solution, expect an interviewer to probe these variations.

• What if k can be 0? Division and modulo by zero are undefined, so special-case k == 0 to only count subarrays whose sum is already exactly 0.
• What if you need the actual subarray, not just its length? Keep storing the first index per remainder as before, then slice arr from firstIndex + 1 to i once the best pair is identified.
• What if you need to count all subarrays divisible by k instead of just the longest one? Group indices by remainder, then for each group of size m add m * (m - 1) / 2 to the count; the overall complexity stays O(n).
• What if the array arrives as a stream of unknown length? Maintain prefixSum and the remainder map incrementally as each element arrives; the algorithm is already online since it never looks ahead.
• What if you are limited to O(1) extra space? This is not achievable in general without allowing a second pass or re-scanning, since the HashMap is exactly what lets you find the first matching remainder without re-reading the array.

Conclusion

Finding the longest subarray with a sum divisible by k is a strong example of turning a brute force O(n^2) scan into a single linear pass by reasoning about prefix sums and remainders. The core trick, mapping each remainder to its first occurrence, shows up again and again in subarray-sum interview problems.

Try adapting the code above to return the actual subarray instead of just its length, or to handle k = 0 as a special case. You can learn more about Array problems like this one on the Arrays category page.