Subarray Sums Divisible by K
Problem Description
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
Example 2:
Input: nums = [5], k = 9
Output: 0
Constraints:
- 1 <= nums.length <= 3 * 104
- -104 <= nums[i] <= 104
- 2 <= k <= 104
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The most straightforward way to solve the problem is to consider every possible subarray of the given array. For each subarray, compute its sum and check if it’s divisible by K. This approach is simple and works fine for small input sizes.
Steps:
- Initialize a counter to zero which will store the number of subarrays satisfying the condition.
- Iterate over all possible starting points of subarrays.
- For each starting point, iterate over all possible ending points.
- Calculate the sum of the current subarray.
- Check if this sum is divisible by
K. If so, increment the counter. - Return the counter after checking all subarrays.
Code:
- Time Complexity: O(n^2) because we are considering all subarrays.
- Space Complexity: O(1) since we're only using a constant amount of additional space.
2. Remainder + HashMap
Intuition:
The brute force approach works but is inefficient for larger arrays. We can optimize this by leveraging the properties of prefix sums and remainders. If the prefix sum up to i is sum[0..i] and prefix sum up to j is sum[0..j], and both sum[0..i] % K and sum[0..j] % K are equal, then the subarray sum[i+1..j] is divisible by K.
We can use a HashMap to keep track of all seen remainder counts, making it easier to find the potential starting points for subarrays that end at each position in the array.
Steps:
- Initialize a HashMap to store the count of each remainder.
- Keep a running sum of the elements.
- Calculate the remainder of the current sum by
K. - If this remainder has been seen before, it means there's a subarray ending at the current position with a sum divisible by
K. - Update the count of subarrays.
- Update the remainder's count in the HashMap.
Code:
- Time Complexity: O(n) as we traverse the array once.
- Space Complexity: O(K) because the hash map will contain at most
Kdistinct remainders.