Subarray Sums Divisible by K
Medium · Arrays & Hashing · Array · Hash Table · Prefix Sum
Problem
Given an integer array nums and an integer k, return the number of non-empty contiguous subarrays whose sum is divisible by k.
A sum of zero counts as divisible. Negative sums count too when they are an exact multiple of k (for example, -6 is divisible by 3).
Examples
Input: nums = [2,-2,3,0,4], k = 3 Output: 6
The sums of [2,-2], [3], [0], [3,0], [2,-2,3] and [2,-2,3,0] are 0, 3, 0, 3, 3 and 3: six multiples of 3.
Input: nums = [1,1], k = 5 Output: 0
The sums are 1, 1 and 2; none is a multiple of 5.
Input: nums = [5,10,5], k = 5 Output: 6
Every value is a multiple of 5, so all six subarrays count.
Constraints
- 1 <= len(nums) <= 3 · 10^4
- -10^4 <= nums[i] <= 10^4
- 2 <= k <= 10^4
Approaches
- Baseline: every start, running sum — time O(n²), space O(1)
Follow-up
In C++, Java, JavaScript and Go, % of a negative number is negative: -1 % 3 is -1, not 2. Normalize with ((x % k) + k) % k. The same remainder-counting trick answers "does any subarray of length at least 2 have a sum divisible by k" (remember the first index of each remainder instead of a count) and the use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
