Problem Statement

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.

LeetCode

https://leetcode.com/problems/subarray-sums-divisible-by-k/description/

Constraints

1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
2 <= k <= 10^4

Examples

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

Different Approaches

1️⃣ Brute Force (Triple Loop) TLE

Intuition:

Try all possible subarrays and check whether the sum of each subarray is divisible by k.

Approach:

1. Loop over all start and end indices.
2. For each subarray, calculate the sum and check sum % k == 0.

Code:

int subarraysDivByK(vector<int>& nums, int k) {
    int count = 0;            // To count how many subarrays are divisible by k
    int n = nums.size();      // Length of the input array

    // Step 1: Loop over all possible starting indices of subarrays
    for (int start = 0; start < n; start++) {

        // Step 2: Loop over all possible ending indices for the current starting index
        for (int end = start; end < n; end++) {
            int subarraySum = 0;  // To store sum of current subarray

            // Step 3: Sum up all elements from 'start' to 'end' index
            for (int i = start; i <= end; i++) {
                subarraySum += nums[i];
            }

            // Step 4: Check if this subarray sum is divisible by k
            if (subarraySum % k == 0) {
                count++;  // If divisible, increment the count
            }
        }
    }

    // Step 5: Return the final count of subarrays divisible by k
    return count;
}

Complexity Analysis:

• Time Complexity:O(n^3)
• Space Complexity:O(1)

2️⃣ Double Loop

Intuition:

Avoid recalculating the sum of the same subarray by keeping a running sum in the inner loop.

Approach:

1. Outer loop: start index.
2. Inner loop: end index; keep adding nums[j] to sum.
3. Check if sum % k == 0.

Code:

int subarraysDivByK(vector<int>& nums, int k) {
    int n = nums.size();     // Get the size of the input array
    int count = 0;           // To count subarrays whose sum is divisible by k

    // Step 1: Loop through all possible starting indices of subarrays
    for (int start = 0; start < n; start++) {
        int subarraySum = 0;  // Initialize sum for the current subarray

        // Step 2: For each starting index, extend the subarray to the right
        for (int end = start; end < n; end++) {
            // Add the current element to subarray sum
            subarraySum += nums[end];

            // Step 3: Check if current subarray sum is divisible by k
            if (subarraySum % k == 0) {
                count++;  // If divisible, increment the count
            }
        }
    }

    // Step 4: Return the final count of valid subarrays
    return count;
}

Complexity Analysis:

• Time Complexity:O(n^2)
• Space Complexity:O(1)

3️⃣ Prefix Sum + Hashmap

Intuition:

Suppose you’re trying to find how many subarrays have a sum divisible by k.

The key mathematical observation here is:

If two prefix sums have the same remainder when divided by k, then the subarray between them is divisible by k.

Why?

Let:

• prefixSum[i] be the sum of elements from index 0 to i.
• prefixSum[j] be the sum from 0 to j where j > i.

Then the sum of the subarray (i+1 to j) is:

subarraySum = prefixSum[j] - prefixSum[i]

If prefixSum[j] % k == prefixSum[i] % k, then:

(prefixSum[j] - prefixSum[i]) % k == 0

-> That means this subarray's sum is divisible by k.

So instead of checking all subarrays, we count how many times each remainder has occurred and use that count to determine how many valid subarrays exist.

For the past remainder we can use the map. We can store the remainder in the map with its occurrence count, such that in future we can check for it, whenever we encounter the same remainder.

Approach:

1. Use a Hash Map remainderFrequency:
   1. Key: remainder of the prefix sum when divided by k
   2. Value: number of times this remainder has occurred
2. Initialize remainderFrequency[0] = 1:
   1. This accounts for subarrays that start from the beginning of the array and are divisible by k.
3. Loop through the array:
   1. Maintain a running sum (prefixSum)
   2. Compute remainder = prefixSum % k
   3. Handle negative remainders by adding k (to get a valid positive remainder)
   4. If this remainder is already in the map, add its count to the result
   5. Increment the frequency of this remainder in the map

Code:

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        // Map to store the frequency of each remainder when prefixSum % k
        unordered_map<int, int> remainderFrequency;

        // Initialize with remainder 0 (for subarrays that start from index 0)
        remainderFrequency[0] = 1;

        int prefixSum = 0;      // Cumulative sum of elements
        int totalSubarrays = 0; // Count of valid subarrays divisible by k

        for (int i = 0; i < nums.size(); i++) {
            // Add current number to prefix sum
            prefixSum += nums[i];

            // Calculate remainder of the prefix sum divided by k
            int remainder = prefixSum % k;

            // If remainder is negative, convert it to a positive equivalent
            if (remainder < 0) {
                remainder += k;
            }

            // If this remainder has been seen before,
            // it means there are subarrays ending at current index
            // that have a sum divisible by k
            if (remainderFrequency.find(remainder) != remainderFrequency.end()) {
                totalSubarrays += remainderFrequency[remainder];
            }

            // Record the occurrence of this remainder
            remainderFrequency[remainder]++;
        }

        // Return total valid subarrays found
        return totalSubarrays;
    }
};

Complexity Analysis:

• Time Complexity:O(n)
  • We iterating through the array once.
• Space Complexity:O(k)
  • In the worst case, the number of unique remainders we can get from prefixSum % k is at most k (from 0 to k-1).
  • So, the hash map will store at most k keys.