974. Subarray Sums Divisible by K

---

Description

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
  • In worst case scenario, if time complexity is O(n2), then it will be (3 * 104)2 operations.
  • We need to find a solution with time complexity O(n * log n) or lesser.
• 104 <= nums[i] <= 104
• 2 <= k <= 104

---

Simple Problem Breakdown

If subarray is divisible by k, then it must be the multiple of k.

We can come up with the following equation: \(A-B=n*k\), where \(A\) is running prefixSum array and \(B\) is the previous prefixSum array. \(A-B=n*k\) can be rearranged as \(B=A-(n*k)\).

To get rid of n we can MOD every element by k, and it will become \(B\,\%\,k=A\,\%\,k-(n*k)\,\%\,k\).

\((n*k)\,\%\,k\) will be 0 as n is the multiple of k so it will always return 0. And the final equation becomes \(B\,\%\,k=A\,\%\,k\).

Based on final equation, we can conclude that we just need to compare the total MOD of running prefixSum array is equal to any previous MOD of prefixSum array.

Solution 1: Brute Force Approach (Prefix Sums + Array)

Intuition

Here's the slighly different explanation compared to the above one, but the idea is the same.

We want to find the number of subarrays whose sum is divisible by k. We can do this by iterating through all the subarrays and checking if the sum of the subarray is divisible by k.

Let's set the following variables:

• \(a_i\) prefixSum[i] = nums[0] + nums[1] + ... + nums[i]
• \(b_j\) prefixSum[j] = nums[0] + nums[1] + ... + nums[j]
• \(r_i\) remainder[i] = \(a_i\) MOD k
• \(r_j\) remainder[j] = \(b_j\) MOD k

If remainder of \(a_i\) and \(b_j\) are equal, then the sum of the subarray between \(i\) and \(j\) is divisible by k, which means the subarrays are what we are looking for.

\(a_i\,\%\,k=b_j\,\%\,k\)
\(=(a_j-b_i)\,\%\,k\)
\(=(a_i\%k + b_j\%k) \%k\)
\(=0 \%k\)
\(=0\)

So the equation \((a_j-b_i)\,\%\,k\) is equal to 0.

By using this approach, we will face Time Limit Exceeded error for the given constraints.

TypeScript

Brute Force Approach 1

The reason why it has a space complexity of O(n) is because we have to store the prefix sum of the array in a separate array.

// Time Complexity: O(n^2)
// Space Complexity: O(n)
function subarraysDivByK(nums: number[], k: number): number {
    let counter = 0;
    let prefixSum: number[] = new Array(nums.length + 1).fill(0);

    for (let i = 0; i < nums.length; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j <= nums.length; j++) {
            if ((prefixSum[j] - prefixSum[i]) % k === 0) {
                counter++;
            }
        }
    }

    return counter;
}

Brute Force Approach 2 (Optimized)

// Time Complexity: O(n^2)
// Space Complexity: O(1)
function subarraysDivByK(nums: number[], k: number): number {
    let count = 0;

    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        for (let j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum % k === 0) {
                count++;
            }
        }
    }
    return count;
};

Solution 2: Prefix Sums + Counting

Intuition

Here's the another explanation for the same idea.

Based on Division Algorithm, Any integer number equal to divisor * quotient + remainder where divisor is \(k\) and quotient is the integer division of the number by \(k\) and remainder is the remainder of the number divided by \(k\).

Let's set the following variables:

• \(a_i\) prefixSum[i] = \(A * k + r_1\)
• \(b_j\) prefixSum[j] = \(B * k + r_2\)

\(b_j - a_i\)
\(=((B * k) + r_2) - ((A * k) + r_1)\)
\(=(B * k) - (A * k) + (r_2 - r_1)\)
\(= k * (B - A) + (r_2 - r_1)\)

If \(k * (B - A)\) is divisible by k, then \(r_2 - r_1\) should be divisible by k as well in order to make the whole equation is divisible by k. So \(r_2 - r_1 = C * k\), where \(C\) is an integer. Rearranging the equation, we get \(r_2 = C * k + r_1\).

TypeScript

Prefix Sums + Counting

Input: [4,5,0,-2,-3,1], k = 5

Initial Variables:

Visual Representation

graph TD
    classDef default text-align:left,font-size: 12px;

    init["`
    mod: 0
    prefixMod: 0
    numOfSubArrays: 0
    modGroups: [1, 0, 0, 0, 0]
    `"]

    loop1["`
    mod: 0 + 4 % 5 = 4
    prefixMod: ( 4 + 5 ) % 5 = 4
    modGroups[4]: 0
    numOfSubArrays: 0 + 0 = 0
    modGroups:[1, 0, 0, 0, 1]
    `"]

    loop2["`
    mod: 4 + 5 % 5 = 4
    prefixMod: ( 4 + 5 ) % 5 = 4
    modGroups[4]: 1
    numOfSubArrays: 0 + 1 = 1
    modGroups:[1, 0, 0, 0, 2]`"]

    loop3["`
    mod: 4 + 0 % 5 = 4
    prefixMod: (4 + 0) % 5 = 4
    modGroups[4]: 2
    numOfSubArrays: 1 + 2 = 3
    modGroups = [1, 0, 0, 0, 3]
    `"]

    loop4["`
    mod: 4 + -2 % 5 = 2
    prefixMod: (2 + 5) % 5 = 2
    modGroups[2]: 0
    numOfSubArrays: 3 + 0 = 3
    modGroups = [1, 0, 1, 0, 3]
    `"]

    loop5["`
    mod: 2 + -3 % 5 = -1
    prefixMod: (-1 + 5) % 5 = 4
    modGroups[4]: 3
    numOfSubArrays: 3 + 3 = 6
    modGroups = [1, 0, 1, 0, 4]
    `"]

    loop6["`
    mod: 4 + 1 % 5 = 0
    prefixMod: (0 + 5) % 5 = 0
    modGroups[0]: 1
    numOfSubArrays: 6 + 1 = 7
    `"]


    init -->|Loop 1|loop1
    loop1 -->|Loop 2|loop2
    loop2 -->|Loop 3|loop3
    loop3 -->|Loop 4|loop4
    loop4 -->|Loop 5|loop5
    loop5 -->|Loop 6|loop6

function subarraysDivByK(nums: number[], k: number): number {
    let n = nums.length;

    // Store the remainder of the prefix sum of the array up to the current index.
    // The prefix sum is a kind of partial sum where the sum includes all elements from the start of the array to the current index.
    let prefixMod = 0;

    // Store the count of subarrays that are divisible by k.
    let numOfSubArrays = 0;

    // There are k mod groups 0...k-1.
    let modGroups: number[] = new Array(k).fill(0);
    modGroups[0] = 1;

    for (let num of nums) {
        // [mod] is the sum of the current prefix sum and the current number modulo k.
        // This is essentially a partial sum of the array up to the current index, but instead of the actual sum, we're storing the sum modulo k.
        let mod = prefixMod + num % k ;

        // [num] could be negative, so we add [k] and modulo [k] again to avoid negative remainders
        // [prefixMod] is the sum of the current prefix sum and the current number modulo k.
        // Again, this is a partial sum of the array up to the current index, but we're storing the sum modulo k.
        prefixMod = (mod + k) % k;

        // Add the number of subarrays up to the current index that are divisible by k.
        // Each of these subarrays represents a different partial sum of the array.
        numOfSubArrays += modGroups[prefixMod];

        // Increment the count of subarrays that are divisible by k.
        // Each increment represents a new partial sum that is divisible by k.
        modGroups[prefixMod]++;
    }

    return numOfSubArrays;
}

Similar Problems

• 523. Continuous Subarray Sum