Subarray Sums Divisible by K

Medium
670.

Subarray Sums Divisible by K

Subarray Sums Divisible by K is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon, Google and Goldman Sachs interviews.

Given an array nums and an integer k, return the number of non-empty contiguous subarrays whose sum is divisible by k.

Example 1

Input
nums = [4,5,0,-2,-3,1], k = 5
Output
7
Explanation
Seven subarrays have a sum that is a multiple of 5, including the whole array and the single 0.

Example 2

Input
nums = [5], k = 9
Output
0

Example 3

Input
nums = [-1,2,9], k = 2
Output
2
Explanation
[2] and [-1,2,9].

Constraints

  • 1 <= nums.length <= 30000
  • -10000 <= nums[i] <= 10000
  • 2 <= k <= 10000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraysDivByK = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Subarray Sums Divisible by K — Problem & Solution

Subarray Sums Divisible by K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Subarray Sums Divisible by K is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon, Google and Goldman Sachs interviews.

Problem statement

Given an array nums and an integer k, return the number of non-empty contiguous subarrays whose sum is divisible by k.

Example 1

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: Seven subarrays have a sum that is a multiple of 5, including the whole array and the single 0.

Example 2

Input: nums = [5], k = 9
Output: 0

Example 3

Input: nums = [-1,2,9], k = 2
Output: 2
Explanation: [2] and [-1,2,9].

Constraints

  • 1 <= nums.length <= 30000
  • -10000 <= nums[i] <= 10000
  • 2 <= k <= 10000

Hints for Subarray Sums Divisible by K

  1. Hint 1

    A subarray sum is P[j] - P[i], so it is divisible by k exactly when P[i] and P[j] leave the same remainder.

  2. Hint 2

    So count, for each remainder, how many prefixes produce it — then every pair of them is one subarray.

  3. Hint 3

    Negative numbers make the language's % go negative; normalise with ((x % k) + k) % k.

How to solve Subarray Sums Divisible by K

Reduce the prefix sums modulo k. Two prefixes with the same remainder bracket a subarray divisible by k, so the answer is the number of equal-remainder pairs.

Approach

  1. Start a remainder tally with count[0] = 1, standing for the empty prefix.
  2. Sweep the array keeping the running prefix sum reduced mod k (normalised to be non-negative).
  3. Before recording the current remainder, add its existing tally to the answer — those are all the earlier prefixes that pair with this one.
  4. Increment the tally and continue.

Why it works

(P[j] - P[i]) % k == 0 is the same as P[j] % k == P[i] % k, so counting pairs of equal remainders counts exactly the qualifying subarrays. Seeding count[0] = 1 is what lets subarrays starting at index 0 be found.

Complexity

  • Time — O(n)
  • Space — O(k)

Pitfalls

  • Forgetting the count[0] = 1 seed drops every subarray that starts at the beginning.
  • In C, Java, Go and friends -3 % 5 is -3, not 2 — the double-modulo normalisation is mandatory.
  • Adding the tally after incrementing it counts a prefix as pairing with itself.

Reference solution

Python

from typing import List

def subarraysDivByK(nums: List[int], k: int) -> int:
    count = {0: 1}
    total = 0
    s = 0
    for x in nums:
        s = (s + x) % k
        total += count.get(s, 0)
        count[s] = count.get(s, 0) + 1
    return total

Java

public static int subarraysDivByK(int[] nums, int k) {
    int[] count = new int[k];
    count[0] = 1;
    int sum = 0, total = 0;
    for (int x : nums) {
        sum = ((sum + x) % k + k) % k;
        total += count[sum];
        count[sum]++;
    }
    return total;
}

C++

int subarraysDivByK(vector<int>& nums, int k) {
    vector<int> count(k, 0);
    count[0] = 1;
    int sum = 0, total = 0;
    for (int x : nums) {
        sum = ((sum + x) % k + k) % k;
        total += count[sum];
        count[sum]++;
    }
    return total;
}

JavaScript

var subarraysDivByK = function(nums, k) {
    var count = {};
    count["0"] = 1;
    var sum = 0, total = 0;
    for (var i = 0; i < nums.length; i++) {
        sum = ((sum + nums[i]) % k + k) % k;
        var key = String(sum);
        if (count[key] !== undefined) total += count[key];
        count[key] = (count[key] === undefined ? 0 : count[key]) + 1;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets