Leetcode 974: Subarray Sums Divisible by K

Input: An integer array nums and an integer k.

Example: nums = [3, 1, -4, 6, 5], k = 3

Constraints:

• 1 <= nums.length <= 3 * 10^4

• -10^4 <= nums[i] <= 10^4

• 2 <= k <= 10^4

Output: An integer representing the count of subarrays where the sum is divisible by k.

Example: 6

Constraints:

• The result must fit within a 32-bit signed integer.

Goal: Count the number of subarrays with a sum divisible by k.

Steps:

• Maintain a running sum of elements as you traverse the array.

• Use the modulo operator to compute the remainder of the running sum when divided by k.

• Adjust negative remainders to ensure they fall within the range [0, k-1].

• Store the frequency of each remainder in a hashmap and use it to count subarrays with matching remainders.

Goal: Ensure inputs follow the problem's constraints.

Steps:

• 1 <= nums.length <= 3 * 10^4

• -10^4 <= nums[i] <= 10^4

• 2 <= k <= 10^4

Assumptions:

• The array nums is valid and non-empty.

• The integer k is greater than or equal to 2.

• Input: nums = [3, 1, -4, 6, 5], k = 3

• Explanation: The total subarrays with sums divisible by k = 3 are 6, including single-element subarrays like [3] and multi-element subarrays like [3, 1, -4, 6, 5].

• Input: nums = [7, -3, 2, 8], k = 4

• Explanation: The subarrays [-3, 2, 8], [2, 8], [8], and [7, -3, 2] have sums divisible by k = 4, resulting in a count of 4.

Approach: Use a hashmap to count the frequency of remainders when the running sum is divided by k, leveraging the remainder property to count subarrays.

Observations:

• A naive approach of computing the sum for all subarrays would be inefficient for large arrays.

• The problem can be optimized using the property of remainders to identify subarrays with sums divisible by k.

• Using a hashmap to track remainder frequencies allows for efficient subarray counting by leveraging previous results.

Steps:

• Initialize a hashmap to store the frequency of remainders, with an initial entry for remainder 0.

• Iterate through the array, maintaining a running sum of elements.

• Compute the remainder of the running sum when divided by k, and adjust negative remainders to fall within [0, k-1].

• Use the hashmap to count the number of subarrays with matching remainders and update the remainder's frequency.

• Return the total count of subarrays.

Empty Inputs:

• An array with one element and k > 1, ensuring no subarray is divisible.

Large Inputs:

• An array of maximum length with varying large values, ensuring efficient handling.

Special Values:

• All elements in the array are 0.

Constraints:

• Ensure that negative remainders are handled correctly.

int subarraysDivByK(vector<int>& nums, int k) {
    int res = 0, n = nums.size(), sum = 0;        
    vector<int> frq(k, 0);
    frq[0] = 1;
    for(int j = 0; j < n; j++) {
        sum += nums[j];
        int rm = sum % k;
        if(rm < 0) rm += k;            
        res += frq[rm];
        frq[rm]++;
    }
    return res;
}

1 : Function Definition

int subarraysDivByK(vector<int>& nums, int k) {

Defines the function `subarraysDivByK`, which takes an integer vector `nums` and an integer `k`, and returns the number of subarrays whose sum is divisible by `k`.

2 : Variable Initialization

    int res = 0, n = nums.size(), sum = 0;

Initializes variables: `res` to store the result (number of valid subarrays), `n` to store the size of `nums`, and `sum` to accumulate the sum of elements as we iterate.

3 : Frequency Array Declaration

    vector<int> frq(k, 0);

Declares a frequency array `frq` of size `k`, initialized with 0, to keep track of the modulo results of subarray sums.

4 : Initial Frequency Setup

    frq[0] = 1;

Sets `frq[0]` to 1, since a sum of 0 is always divisible by `k`, which allows us to count subarrays starting from the first element.

5 : Loop Over Array

    for(int j = 0; j < n; j++) {

Starts a loop to iterate through each element in the `nums` array.

6 : Update Sum

        sum += nums[j];

Adds the current element `nums[j]` to the running sum `sum`.

7 : Modulo Calculation

        int rm = sum % k;

Calculates the remainder `rm` when the accumulated sum is divided by `k`.

8 : Handle Negative Remainders

        if(rm < 0) rm += k;

Adjusts the remainder if it's negative by adding `k` to ensure that `rm` is always positive.

9 : Update Result

        res += frq[rm];

Increments the result `res` by the value stored in `frq[rm]`, which represents the count of subarrays whose sum modulo `k` equals `rm`.

10 : Update Frequency Array

        frq[rm]++;

Increments the frequency count of the remainder `rm` in the frequency array `frq`.

11 : Return Statement

    return res;

Returns the result `res`, which contains the total number of subarrays whose sum is divisible by `k`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The array is traversed once, and hashmap operations are O(1) on average.

Best Case: O(k)

Worst Case: O(k)

Description: The hashmap stores at most k entries for the remainders.

Leetcode 974: Subarray Sums Divisible by K

Explore →