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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question