Problem

Given an array of integers, find subarray such that sum of elements in the element is divisible by k.

Examples

Example 1:

1
2
3

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: [4, 5, 0, -2, -3, 1]
Explanation: The sum of the output subarray is 5, which is divisible by 5.

Example 2:

1
2
3

Input: nums = [2, 7, 6, 1, 4, 5], k = 3
Output: [2, 7, 6]
Explanation: The subarray [2, 7, 6] has a sum of 15, which is divisible by 3.

Similar Problem

Subarray Sums Divisible by K

Solution

Method 1 - Using Prefix sum and modulo k

  1. Prefix Sum and Modulo:
    • Use a dictionary to store the first occurrence of each prefix sum modulo k.
  2. Collision Principle:
    • If two prefix sums have the same remainder when divided by k, the elements between these two prefix sums form a subarray whose sum is divisible by k.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public class Solution {
    public int[] subarrayDivByK(int[] nums, int k) {
        Map<Integer, Integer> prefixSumModMap = new HashMap<>();
        prefixSumModMap.put(0, -1);
        int sum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int mod = ((sum % k) + k) % k;

            if (prefixSumModMap.containsKey(mod)) {
                int start = prefixSumModMap.get(mod) + 1;
                int end = i;
                int[] result = new int[end - start + 1];
                for (int j = start; j <= end; j++) {
                    result[j - start] = nums[j];
                }
                return result;
            }
            prefixSumModMap.put(mod, i);
        }

        return new int[0];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums1 = {2, 7, 6, 1, 4, 5};
        int k1 = 3;
        int[] result1 = sol.subarrayDivByK(nums1, k1);
        System.out.println("Subarray: " + java.util.Arrays.toString(result1));  // Expected output: [2, 7, 6]

        int[] nums2 = {1, 3, 2, 6, 4};
        int k2 = 7;
        int[] result2 = sol.subarrayDivByK(nums2, k2);
        System.out.println("Subarray: " + java.util.Arrays.toString(result2));  // Expected output: [3, 2, 6]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def subarrayDivByK(self, nums: List[int], k: int) -> List[int]:
        prefix_sum_mod_map = {0: -1}
        total_sum = 0
        
        for i in range(len(nums)):
            total_sum += nums[i]
            mod = ((total_sum % k) + k) % k
            
            if mod in prefix_sum_mod_map:
                start = prefix_sum_mod_map[mod] + 1
                end = i
                return nums[start:end + 1]
            
            prefix_sum_mod_map[mod] = i
        
        return []

# Example usage
sol = Solution()
nums1 = [2, 7, 6, 1, 4, 5]
k1 = 3
result1 = sol.subarrayDivByK(nums1, k1)
print("Subarray:", result1)  # Expected output: [2, 7, 6]

nums2 = [1, 3, 2, 6, 4]
k2 = 7
result2 = sol.subarrayDivByK(nums2, k2)
print("Subarray:", result2)  # Expected output: [3, 2, 6]

Complexity

  • ⏰ Time complexity: O(n), where n is the number of elements in the array because we traverse the array once.
  • 🧺 Space complexity: O(n), for storing the prefix sums and their indices in a dictionary.

Similar Problem

Another variation of this problem could be:

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

Similar to above approach, but instead of keeping a single index for each prefix sum modulo k, we maintain a list of indices with the same prefix sum modulo k. Each pair of indices from these lists represents a potential subarray. Continuously update the maximum size from these candidate subarrays to find the answer.