Problem Statement

Given an array of integers nums and an integer k, return the count of non-empty subarrays that have a sum that is divisible by k.

A subarray is a continuous part of an array.

Examples

Example 1

• Input: nums = [3, 1, 2, -2, 5, -1], k = 3
• Expected Output: 7
• Justification: The subarrays that sum to a multiple of 3 are [3], [1, 2], [3, 1, 2], [3, 1, 2, -2, 5], [1, 2, -2, 5], [-2, 5], and [2, -2].

Example 2

• Input: nums = [4, 5, 0, -2, -3, 1], k = 5
• Expected Output: 7
• Justification: The subarrays that sum to a multiple of 5 are [5], [4, 5, 0, -2, -3, 1], [5, 0], [0], [5, 0, -2, -3], [0, -2, -3], and [-2, -3].

Example 3

• Input: nums = [-1, 2, 9], k = 2
• Expected Output: 2
• Justification: The subarrays that sum to a multiple of 2 are [2] and [-1, 2, 9].

Constraints:

• 1 <= nums.length <= 3 * 10⁴
• -10⁴ <= nums[i] <= 10⁴
• 2 <= k <= 10⁴

Solution

To solve this problem, we will use a hash map (dictionary) to keep track of the cumulative sums and their remainders when divided by k. This helps in finding the number of subarrays whose sum is divisible by k. The idea is to iterate through the array while maintaining a running sum. For each element, calculate the cumulative sum and its remainder when divided by k. If this remainder has been seen before, it indicates that there is a subarray which sum is divisible by k. By using the hash map to store and count these remainders, we efficiently count the subarrays without needing nested loops, making the approach more efficient.

This approach works because it leverages the properties of modular arithmetic to efficiently determine subarrays that meet the criteria. Using a hash map to store the counts of remainders enables us to quickly check for existing subarrays that, when combined with the current element, form a subarray whose sum is divisible by k.

Step-by-step Algorithm

• Initialize a hash map remainder_count to store the frequency of remainders. Start with {0: 1} to handle cases where the subarray itself is divisible by k.
• Initialize cumulative_sum to 0 and count to 0.
• Iterate through each element in nums:
  • Add the current element to cumulative_sum.
  • Compute the remainder of cumulative_sum divided by k.
  • If the remainder is negative, adjust it by adding k.
  • If the remainder is already in remainder_count, increment count by the value associated with the remainder in the hash map.
  • Increment the count of this remainder in the hash map.
• Return count.

Algorithm Walkthrough

Using the input = nums = [3, 1, 2, -2, 5, -1] and k = 3.

1. Initialization:

   • remainder_count = {0: 1}
   • cumulative_sum = 0
   • count = 0

2. Iteration 1 (num = 3):

   • cumulative_sum = 3
   • remainder = 3 % 3 = 0
   • count += remainder_count[0] = 1 -> count = 1
   • Update remainder_count: {0: 2}

3. Iteration 2 (num = 1):

   • cumulative_sum = 4
   • remainder = 4 % 3 = 1
   • count += remainder_count.get(1, 0) = 0 -> count = 1
   • Update remainder_count: {0: 2, 1: 1}

4. Iteration 3 (num = 2):

   • cumulative_sum = 6
   • remainder = 6 % 3 = 0
   • count += remainder_count[0] = 2 -> count = 3
   • Update remainder_count: {0: 3, 1: 1}

5. Iteration 4 (num = -2):

   • cumulative_sum = 4
   • remainder = 4 % 3 = 1
   • count += remainder_count[1] = 1 -> count = 4
   • Update remainder_count: {0: 3, 1: 2}

6. Iteration 5 (num = 5):

   • cumulative_sum = 9
   • remainder = 9 % 3 = 0
   • count += remainder_count[0] = 3 -> count = 7
   • Update remainder_count: {0: 4, 1: 2}

7. Iteration 6 (num = -1):

   • cumulative_sum = 8
   • remainder = 8 % 3 = 2
   • count += remainder_count.get(2, 0) = 0 -> count = 7
   • Update remainder_count: {0: 4, 1: 2, 2: 1}

The total count of subarrays whose sum is divisible by k is 7.

Code

Complexity Analysis

Time Complexity

The time complexity of the algorithm is O(n), where (n) is the number of elements in the input array nums. This is because we traverse the array exactly once, performing constant-time operations for each element.

Space Complexity

The space complexity of the algorithm is O(k), where (k) is the value of the divisor. This is due to the hash map (or dictionary) that stores at most (k) different remainders. In the worst case, the hash map will store all possible remainders from (0) to (k-1).