Arrays and Hashing Prefix sums
79. Subarray Sums Divisible by K
You are given an array of integers nums and a positive integer k. Return the number of subarrays whose
sum is divisible by k.
A subarray is a contiguous sequence of elements from nums. Two subarrays are different if they start or
end at different positions. A sum is divisible by k when it is a whole multiple of k: 0, k, -k, 2k
and so on.
Example 1
Input: nums = [3, -1, 2, 4, -6], k = 3
4Explanation: Four subarrays have a sum divisible by 3: [3] with sum 3, [2, 4] with sum 6, [-6] with sum −6, and
[2, 4, -6] with sum 0.
Example 2
Input: nums = [1, 2, 3, 4], k = 5
2Explanation: [2, 3] adds up to 5 and the whole array adds up to 10. No other subarray sum is a multiple of 5.
Example 3
Input: nums = [-2, -3, 5], k = 5
3Explanation: [-2, -3] adds up to −5, [5] to 5 and the whole array to 0. All three are multiples of 5.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 1091 ≤ k ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.