Longest subarray with sum divisible by k

Given an arr[] containing n integers and a given positive integer k. The problem is to find the longest subarray’s length with the sum of the elements divisible by the given value k.

Example 1

Input: arr[] = {2, 7, 6, 1, 4, 5}, k = 3

Output: 4

Explanation: The subarray is {7, 6, 1, 4} with sum 18, which is divisible by 3.

Example 2

Input: arr[] = {-2, 2, -5, 12, -11, -1, 7}, k = 3

Output: 5

Approach

1. Initialize a hashmap to store cumulative sums modulo k along with their indices. Initially, add (0, -1) to handle cases starting at index 0. This hashmap will help keep track of previously encountered cumulative sums that have the same modulo value.
2. Initialize two variables: maxSubarrayLength to keep track of the longest subarray length, and currentSum to store the cumulative sum of the elements.
3. Iterate through the input array, processing each element from left to right.
4. For each element, update currentSum by adding the element's value.
5. Calculate the modulo value of currentSum using the positive integer k.
6. Check if the calculated modulo value exists in the hashmap. If it does, update maxSubarrayLength by finding the difference between the current index and the index stored in the hashmap for that modulo value. This represents the length of the subarray with a sum divisible by k.
7. If the modulo value is not in the hashmap, add it to the hashmap with the current index as the value.
8. Continue this process for all elements in the array, keeping track of the maximum subarray length.
9. After iterating through the entire array, maxSubarrayLength will contain the length of the longest subarray with a sum divisible by k. Return this value as the result.

Complexity

• Time Complexity: O(n), where 'n' is the length of the input array
• Space Complexity: O(min(n, k)), where 'n' is the length of the input array and 'k' is the given positive integer.

Java Code

import java.util.HashMap;
import java.util.Arrays;


public class LongestSubarraySumDivisibleByK {
    public int maxSubarrayDivByK(int[] arr, int k) {
        int n = arr.length;
        int maxSubarrayLength = 0;
        int currentSum = 0;

        // Create a hashmap to store cumulative sums modulo k
        HashMap<Integer, Integer> moduloSumMap = new HashMap<>();
        moduloSumMap.put(0, -1);  // Initialize with 0 at -1 index to handle cases starting at index 0

        for (int i = 0; i < n; i++) {
            currentSum += arr[i];
            int modulo = (currentSum % k + k) % k;  // Ensure positive modulo value

            if (moduloSumMap.containsKey(modulo)) {
                int prevIndex = moduloSumMap.get(modulo);
                maxSubarrayLength = Math.max(maxSubarrayLength, i - prevIndex);
            } else {
                moduloSumMap.put(modulo, i);
            }
        }

        return maxSubarrayLength;
    }

    public static void main(String[] args) {
        LongestSubarraySumDivisibleByK solution = new LongestSubarraySumDivisibleByK();
        int[] arr = {2, 7, 6, 1, 4, 5};
        int k = 3;
        int result = solution.maxSubarrayDivByK(arr, k);
        System.out.println("Given array: " + Arrays.toString(arr));
        System.out.println("Longest subarray length with sum divisible by " + k + ": " + result);
    }
}

Output

Given array: [2, 7, 6, 1, 4, 5]
Longest subarray length with sum divisible by 3: 4