Subarray Sums Divisible by K

Med

#0928Time: O(N^2), where N is the number of elements in the `nums` array. The two nested loops lead to a quadratic number of operations as we calculate the sum for each of the N*(N+1)/2 subarrays.Space: O(1), as we only use a constant amount of extra space for variables like `count` and `currentSum`.4 companies

Patterns

Prefix Sum

Data structures

Array Hash Table

Companies

Expedia Tinkoff Citadel thoughtspot

Prompt

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 * 10⁴
-10⁴ <= nums[i] <= 10⁴
2 <= k <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to generate every possible contiguous subarray, calculate the sum of its elements, and then check if that sum is divisible by k. If it is, we increment a counter. This method is easy to conceptualize but computationally expensive.

Algorithm

Initialize a counter count to 0.
Use a nested loop structure to iterate through all possible subarrays.
- The outer loop with index i determines the start of the subarray.
- The inner loop with index j determines the end of the subarray.
For each subarray defined by i and j, calculate its sum.
- Initialize a currentSum to 0 before the inner loop.
- In the inner loop, accumulate the sum by adding nums[j] to currentSum.
Check if the currentSum is divisible by k (i.e., currentSum % k == 0).
If the condition is met, increment the count.
After all subarrays have been checked, return the final count.

Walkthrough

This approach uses two nested loops to define the boundaries of each subarray. The outer loop iterates from the first element to the last, fixing the starting point of the subarray. The inner loop then iterates from this starting point to the end of the array, defining the ending point. For each subarray generated, we maintain a running sum. After adding each new element to the subarray, we check if the current running sum is divisible by k. We keep a total count of all such subarrays found.

1class Solution {2    public int subarraysDivByK(int[] nums, int k) {3        int count = 0;4        for (int i = 0; i < nums.length; i++) {5            int currentSum = 0;6            for (int j = i; j < nums.length; j++) {7                currentSum += nums[j];8                if (currentSum % k == 0) {9                    count++;10                }11            }12        }13        return count;14    }15}

Complexity

Time

O(N^2), where N is the number of elements in the `nums` array. The two nested loops lead to a quadratic number of operations as we calculate the sum for each of the N*(N+1)/2 subarrays.

Space

O(1), as we only use a constant amount of extra space for variables like `count` and `currentSum`.

Trade-offs

Pros

Simple to understand and implement.
Requires no extra space other than a few variables.

Cons

Highly inefficient for larger arrays.
Will likely result in a 'Time Limit Exceeded' (TLE) error on most online judges for the given constraints.

A highly efficient approach can be devised using prefix sums and modular arithmetic. The core idea is that if two prefix sums have the same remainder when divided by k, the sum of the elements between them is divisible by k. We can find these pairs in a single pass through the array.

Algorithm

Initialize count = 0, prefixSum = 0.
Create a frequency array, remainderFreq, of size k and initialize all its elements to 0.
Set remainderFreq[0] = 1. This is a crucial base case to account for subarrays that start from index 0 and have a sum divisible by k.
Iterate through each number num in the input array nums:
- Add the current number to prefixSum: prefixSum += num.
- Calculate the remainder of the prefixSum with respect to k. To handle potential negative results from the modulo operator (e.g., in Java), use the formula remainder = (prefixSum % k + k) % k.
- If this remainder has been seen before, it means there are remainderFreq[remainder] previous prefix sums that can form a valid subarray with the current one. Add this frequency to the count: count += remainderFreq[remainder].
- Increment the frequency of the current remainder in the map: remainderFreq[remainder]++.
Return count.

Walkthrough

Let prefixSum[i] be the sum of elements from nums[0] to nums[i]. The sum of a subarray nums[i...j] is prefixSum[j] - prefixSum[i-1]. We are looking for cases where (prefixSum[j] - prefixSum[i-1]) % k == 0. This is equivalent to prefixSum[j] % k == prefixSum[i-1] % k.

This transforms the problem into finding pairs of prefix sums that have the same remainder when divided by k. We can solve this by iterating through the array once, calculating the running prefix sum, and using a hash map or an array to store the frequencies of the remainders encountered so far.

For each element, we calculate the current prefix sum's remainder. If we have seen this remainder f times before, it means we can form f new subarrays ending at the current position whose sums are divisible by k. We add f to our total count and then update the frequency of the current remainder.

1class Solution {2    public int subarraysDivByK(int[] nums, int k) {3        // Use an array to store frequencies of remainders. Size k for remainders 0 to k-1.4        int[] remainderFreq = new int[k];5        // A prefix sum of 0 (before starting) has a remainder of 0. This is our base case.6        remainderFreq[0] = 1;7 8        int count = 0;9        int prefixSum = 0;10 11        for (int num : nums) {12            prefixSum += num;13            // Calculate remainder, handling negative results from Java's % operator.14            int remainder = (prefixSum % k + k) % k;15            16            // Add the number of times we've seen this remainder before to our count.17            count += remainderFreq[remainder];18            19            // Increment the frequency of the current remainder.20            remainderFreq[remainder]++;21        }22 23        return count;24    }25}

Complexity

Time

O(N), where N is the number of elements in the `nums` array. We only need to iterate through the array once.

Space

O(k), where `k` is the divisor. We use an auxiliary array of size `k` to store the frequencies of the remainders. Since `k` is at most 10^4, this is considered efficient.

Trade-offs

Pros

Optimal time complexity.
Efficiently handles large inputs within the given constraints.

Cons

Requires understanding of modular arithmetic and the prefix sum technique.
Uses extra space proportional to k.

Solutions

Solution

1class Solution {2public3  int subarraysDivByK(int[] nums, int k) {4    Map<Integer, Integer> cnt = new HashMap<>();5    cnt.put(0, 1);6    int ans = 0, s = 0;7    for (int x : nums) {8      s = ((s + x) % k + k) % k;9      ans += cnt.getOrDefault(s, 0);10      cnt.merge(s, 1, Integer : : sum);11    }12    return ans;13  }14}

1class Solution {2public:3  int subarraysDivByK(vector<int> &nums, int k) {4    unordered_map<int, int> cnt{{0, 1}};5    int ans = 0, s = 0;6    for (int &x : nums) {7      s = ((s + x) % k + k) % k;8      ans += cnt[s]++;9    }10    return ans;11  }12};

1class Solution:2    def subarraysDivByK(self, nums: List[int], k: int) -> int: cnt = Counter({0: 1}) ans = s = 0 for x in nums: s = (s + x) % k ans += cnt[s] cnt[s] += 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem