Longest subarray with sum divisible by k

https://www.geeksforgeeks.org/longest-subarray-sum-divisible-k/

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

Examples:

Input : arr[] = {2, 7, 6, 1, 4, 5}, k = 3
Output : 4
The subarray is {7, 6, 1, 4} with sum 18,
which is divisible by 3.

Method 1 (Naive Approach): Consider all the subarrays and return the length of the subarray with sum divisible by k and has the longest length.
Time Complexity: O(n2).

Method 2 (Efficient Approach): Create an array mod_arr[] where mod_arr[i] stores (sum(arr[0]+arr[1]..+arr[i]) % k). Create a hash table having tuple as (ele, idx), where ele represents an element of mod_arr[] and idx represents the element’s index of first occurrence in mod_arr[]. Now, traverse mod_arr[] from i = 0 to n and follow the steps given below.

1. If mod_arr[i] == 0, then update maxLen = (i + 1).
2. Else if mod_arr[i] is not present in the hash table, then create tuple (mod_arr[i], i) in the hash table.
3. Else, get the value associated with mod_arr[i] in the hash table. Let this be idx.
4. If maxLen < (i – idx), then update maxLen = (i – idx).

    static int longSubarrWthSumDivByK(int arr[], 

                                      int n, int k)

    {

        // unodered map 'um' implemented as

        // hash table

        HashMap<Integer, Integer> um= new HashMap<Integer, Integer>();

          

        // 'mod_arr[i]' stores (sum[0..i] % k)

        int mod_arr[]= new int[n];

        int max = 0;

        int curr_sum = 0;

          

        // traverse arr[] and build up the

        // array 'mod_arr[]'

        for (int i = 0; i < n; i++)

        {

            curr_sum += arr[i];

              

            // as the sum can be negative, 

            // taking modulo twice

            mod_arr[i] = ((curr_sum % k) + k) % k;     

        } 

          

        for (int i = 0; i < n; i++)

        {

            // if true then sum(0..i) is 

            // divisible by k

            if (mod_arr[i] == 0)

                // update 'max'

                max = i + 1;

              

            // if value 'mod_arr[i]' not present in 'um'

            // then store it in 'um' with index of its

            // first occurrence     

            else if (um.containsKey(mod_arr[i]) == false)

                um.put(mod_arr[i] , i);

                  

            else

                // if true, then update 'max'

                if (max < (i - um.get(mod_arr[i])))

                    max = i - um.get(mod_arr[i]);         

        }

          

        // required length of longest subarray with

        // sum divisible by 'k'

        return max;

    }    




http://www.zrzahid.com/subarray-with-sum-divisible-by-k/

We can do some math for this problem.  Let A[i] to A[[j] is such a subarray i.e.

               (A[i]+A[i+1]+...+A[j])%K = 0. Which is equivalent to
           <=> (A[0]+A[1]+....+A[j])%K = (A[0]+A[1]+...A[i])%K

1. So we need to find such a pair of indices (i, j) that they satisfy the above condition.
2. Find Cumulative sum and get mod K of the sum for each position
3. Now, subarray by each pair of positions with same value of cumsum mod k constitute a continuous range whose sum is divisible by K.

public static int[] SubArraySumModK(final int A[], final int K) {
    int sum = 0;
    final Map<Integer, Integer> candidates = new HashMap<Integer, Integer>();

    for (int i = 0; i < A.length; i++) {
        sum += A[i];
        if (!candidates.containsKey(sum % K)) {
            candidates.put(sum % K, i);
        } else {
            // a subarray found
            return Arrays.copyOfRange(A, candidates.get(sum % K) + 1, i+1);
        }
    }
    return null;
}

Another variation of this problem could be

Given an array of random integers, find max length subarray such that sum of elements in the element is equal a given number.

Similar approach as above. Instead of keeping one index per cumsum (mod k) we now need to maintain a list of indices that have same cumsum. Each pair of these lists is a candidate subarray. So, keep updating the max size among subarrays. Thats is our answer.