Command Palette

Search for a command to run...

Hectal
Problem 42.2 · Pattern Recognition DrillsMedium

Subarray Sums Divisible by K

What it teaches:

Practise it on judges as “Subarray Sums Divisible by K”.

In plain words

Walk along the numbers keeping a running total, and note only its remainder when divided by k. If the running total had the same remainder at two different moments, the numbers between those moments add up to a multiple of k. So at each step, count how many earlier moments had the same remainder, then record this one.

Return how many non-empty subarrays have a sum divisible by k. Example: nums = [4,5,0,-2,-3,1], k = 5 → 7.

The problem

Return the number of non-empty subarrays whose sum is divisible by k.

Example 1

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

Constraints

  • 1 ≤ n ≤ 3 × 10⁴
  • Negative numbers allowed

Pattern clues in the wording

  • → Count subarrays
  • → Sum condition
  • → Negatives (no sliding window)

Stuck? Take one hint at a time

Solution · starter
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
nums = [4,5,0,-2,-3,1]
k = 5
7
2
nums = [5]
k = 9
0

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Remainder counts · O(n)
1

Remainder counts

Time O(n) Space O(k)

count[0] = 1. For each prefix remainder r (made non-negative), add count[r], then count[r]++.

▶ Dry run: Count matching remainders of the running sumnums = [4,5,0,-2,-3,1], k = 5
4
0
5
1
0
2
-2
3
-3
4
1
5

remainder counts(map)

0: 1

state(vars)

sum: 0total: 0

Step 1/5Before any number the sum is 0, so remainder 0 has been seen once.

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

Verdict: Subarray Sum Equals K with remainders instead of values.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Negative prefix sums
  • k = 1 (every subarray)

Mistakes people make

  • Using sum % k directly (negative remainders in Java).

Interview

Follow-up questions

What about "subarray of length ≥ 2 with sum a multiple of k" (Continuous Subarray Sum)?