Coding

Count of Subarrays with Sum Divisible by K

Asked at

Morgan Stanley

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array of integers, nums, and an integer k, the task is to find the total number of subarrays whose sum is divisible by k. A subarray is a contiguous portion of the array.

Input: nums = [3, 1, 4, 1], k = 3 Output: 3 Explanation: The subarrays whose sum is divisible by 3 are: [3], [1, 4, 1], [3, 1, 4, 1].

Input: nums = [5, 10, -5, 20], k = 7 Output: 0 Explanation: There is no subarray whose sum is divisible by 7.

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

1 <= nums.length <= 105
-104 <= nums[i] <= 104
2 <= k <= 104

cpp

class Solution{
public:
    int subarraySumDivisbleByK(vector<int> &nums, int k){
        
    }
};

java

class Solution {
    public int subarraySumDivisbleByK(int[] nums, int k) {
        
    }
}

python

class Solution:
    def subarraySumDivisbleByK(self, nums, k):

javascript

class Solution {
    subarraySumDivisbleByK(nums, k) {
      
    }
}

csharp

public class Solution
{
    public int SubarraySumDivisibleByK(int[] nums, int k)
    {
        
    }
}

func subarraySumDivisbleByK(nums []int, k int) int {
	count := 0
	currentSum := 0
	remainderCounts := make(map[int]int)

	remainderCounts[0] = 1

	for _, num := range nums {
		currentSum += num
		remainder := currentSum % k

		if remainder < 0 {
			remainder += k
		}

		count += remainderCounts[remainder]

		remainderCounts[remainder]++
	}

	return count
}

Stuck? Show a way to structure it+

01Initialize frequency of remainder zero to one
02Update running sum and normalize its remainder
03Add previous frequency of that remainder to answer
04Increment the remainder frequency

Reference answer

Start by restating the input contract for Count of Subarrays with Sum Divisible by K and testing the smallest boundary case before choosing the algorithm. Maintain prefix sum modulo k. If two prefixes have the same remainder, the subarray between them has sum divisible by k. Count how many times each remainder has appeared, add that count before incrementing it, and normalize negative remainders. Explain the invariant while coding, then show how each update preserves it. The prefix scan is O(n) time and the remainder-count map uses O(min(n, k)) space. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How would you count sums congruent to r?
Tests: follow-up reasoning
Why is the initial zero frequency one?
Tests: correctness reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question