# Subarray Sums Divisible by K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/subarray-sums-divisible-by-k)
Canonical: https://scaleengineer.com/dsa/problems/subarray-sums-divisible-by-k
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Citadel](https://scaleengineer.com/companies/citadel), [thoughtspot](https://scaleengineer.com/companies/thoughtspot)
---
## Problem
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`

# Approaches
## Brute Force Approach
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.
**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`.
**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.
### Explanation
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.

```java
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int currentSum = 0;
            for (int j = i; j < nums.length; j++) {
                currentSum += nums[j];
                if (currentSum % k == 0) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### 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`.

## Prefix Sum with Hashing
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.
**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.
**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`.
### Explanation
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.

```java
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        // Use an array to store frequencies of remainders. Size k for remainders 0 to k-1.
        int[] remainderFreq = new int[k];
        // A prefix sum of 0 (before starting) has a remainder of 0. This is our base case.
        remainderFreq[0] = 1;

        int count = 0;
        int prefixSum = 0;

        for (int num : nums) {
            prefixSum += num;
            // Calculate remainder, handling negative results from Java's % operator.
            int remainder = (prefixSum % k + k) % k;
            
            // Add the number of times we've seen this remainder before to our count.
            count += remainderFreq[remainder];
            
            // Increment the frequency of the current remainder.
            remainderFreq[remainder]++;
        }

        return count;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int subarraysDivByK(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    cnt.put(0, 1);
    int ans = 0, s = 0;
    for (int x : nums) {
      s = ((s + x) % k + k) % k;
      ans += cnt.getOrDefault(s, 0);
      cnt.merge(s, 1, Integer : : sum);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int subarraysDivByK(vector<int> &nums, int k) {
    unordered_map<int, int> cnt{{0, 1}};
    int ans = 0, s = 0;
    for (int &x : nums) {
      s = ((s + x) % k + k) % k;
      ans += cnt[s]++;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```