Skip to main content
Talentd

Subarray Sums Divisible by K - Solution & Explanation

MediumArrayHash TablePrefix Sum23 min readAsked at: Amazon, Microsoft, Meta +8
Practice this problem

Problem Statement

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2:

Input: nums = [5], k = 9
Output: 0

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • 2 <= k <= 104

Approach Overview

Problem Overview: Given an integer array nums and an integer k, count the number of contiguous subarrays whose sum is divisible by k. The key observation: if two prefix sums leave the same remainder when divided by k, the subarray between them has a sum divisible by k.

Approach 1: Brute Force Subarray Sum (O(n²) time, O(1) space)

Check every possible subarray. Start an index i, then extend the subarray to every j ≥ i while maintaining the running sum. Each time the sum modulo k equals zero, increment the count. This method directly simulates the definition of the problem and helps build intuition about how subarray sums behave. However, the nested iteration over all start and end indices leads to O(n²) time complexity, which becomes slow for large inputs.

Approach 2: Prefix Sums with HashMap (O(n) time, O(k) space)

Use a running prefix sum and track the frequency of remainders prefixSum % k in a hash map. When the same remainder appears again, the subarray between the two indices has a sum divisible by k. For each element, compute the new prefix sum, normalize the remainder using (sum % k + k) % k to handle negative numbers, and check how many times this remainder has appeared before. Add that frequency to the result, then update the map. This transforms the problem into counting matching remainder pairs using a constant‑time hash lookup.

The insight is rooted in prefix sum arithmetic: if prefix[j] % k == prefix[i] % k, then (prefix[j] - prefix[i]) % k == 0, meaning the subarray i+1..j is divisible by k. The hash map stores counts of each remainder so you can accumulate valid subarrays in a single pass.

This solution combines ideas from Prefix Sum, Hash Table, and Array problems. The single linear traversal and constant-time hash operations make it the optimal strategy for large arrays.

Recommended for interviews: Interviewers expect the prefix sum + hash map approach. Brute force demonstrates that you understand subarrays and modular checks, but the O(n) prefix remainder counting technique shows deeper algorithmic thinking and familiarity with common prefix-sum patterns.

Approach 1: Prefix Sums with HashMap

This approach leverages prefix sums and the properties of modular arithmetic to efficiently count subarrays whose sums are divisible by k. By maintaining a hashmap (or dictionary) that keeps track of the frequency of each remainder observed when computing prefix sums modulo k, we can determine how many valid subarrays end at each position in the array.

For any position in the array, if we have the same remainder as a previously computed prefix sum, it indicates that the subarray between the two indices is divisible by k.

In this C implementation, an array is used to store the frequency of each remainder when the cumulative sum is divided by k. We initialize the first element to 1 as a subarray with sum 0 (no elements) is considered valid when dividing by k. We then iterate over the input array, updating the cumulative sum and calculating the current remainder. Each time we find a previously seen remainder in our modCount array, it indicates subarrays ending at the current position are divisible by k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array, as we iterate over the array once.
Space Complexity: O(k), where k is the number of different remainders we track in our modCount array.

Try this approach in the editor →

Approach 2: Brute Force Subarray Sum

The brute force approach involves checking all possible subarrays to find those whose sum is divisible by k. This method is less efficient and should be used primarily for small inputs due to its higher time complexity. We iterate over all subarray starting points and compute the sum for all possible ending positions, counting subarrays that meet the criteria.

This C implementation follows a nested loop technique. The first loop sets potential starting points for subarrays, and the inner loop accumulates sums for subarrays ending at each subsequent index. Each valid subarray whose sum is zero modulo k is counted. This approach is simple but becomes inefficient as input sizes grow.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the number of elements in the array (due to double loop).
Space Complexity: O(1), as only integer counters and accumulators are used.

Try this approach in the editor →

Approach 3: Hash Table + Prefix Sum

Suppose there exists i leq j such that the sum of nums[i,..j] is divisible by k. If we let s_i represent the sum of nums[0,..i] and s_j represent the sum of nums[0,..j], then s_j - s_i is divisible by k, i.e., (s_j - s_i) bmod k = 0, which means s_j bmod k = s_i bmod k. Therefore, we can use a hash table to count the number of prefix sums modulo k, allowing us to quickly determine if there exists a subarray that meets the condition.

We use a hash table cnt to count the number of prefix sums modulo k, where cnt[i] represents the number of prefix sums with a modulo k value of i. Initially, cnt[0] = 1. We use a variable s to represent the prefix sum, initially s = 0.

Next, we traverse the array nums from left to right. For each element x, we calculate s = (s + x) bmod k, then update the answer ans = ans + cnt[s], where cnt[s] represents the number of prefix sums with a modulo k value of s. Finally, we increment the value of cnt[s] by 1 and continue to the next element.

In the end, we return the answer ans.

Note: Since the value of s can be negative, we can add k to the result of s bmod k and then take modulo k again to ensure that the value of s is non-negative.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sums with HashMap

Time Complexity: O(n), where n is the number of elements in the array, as we iterate over the array once.
Space Complexity: O(k), where k is the number of different remainders we track in our modCount array.

Brute Force Subarray Sum

Time Complexity: O(n^2), where n is the number of elements in the array (due to double loop).
Space Complexity: O(1), as only integer counters and accumulators are used.

Hash Table + Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray SumO(n²)O(1)Useful for understanding the problem or when constraints are very small
Prefix Sum + HashMapO(n)O(k)General case and expected interview solution for large arrays

Video Solution

Subarray Sums Divisible by K - Leetcode 974 - Python • NeetCodeIO • 39,986 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Subarray Sums Divisible by K easy or hard?
The problem is classified as Medium because the brute force idea is straightforward but the optimal solution requires recognizing the prefix sum remainder pattern. Understanding how equal remainders imply divisible subarrays is the key insight.
Subarray Sums Divisible by K Python/Java solution
Both Python and Java implementations use the same prefix sum + hash map technique. Track the running sum, compute remainder = (sum % k + k) % k, add the existing frequency of that remainder to the result, and update the map. The algorithm runs in O(n) time with O(k) space.
How to solve Subarray Sums Divisible by K in O(n)?
Maintain a running prefix sum and compute its remainder modulo k at each step. Store how many times each remainder has appeared in a hash map. If the same remainder occurs again, add its frequency to the result because those earlier prefix sums form subarrays whose sums are divisible by k.
What is the best approach for Subarray Sums Divisible by K?
The optimal approach uses prefix sums with a hash map that stores frequencies of remainders when prefix sums are divided by k. If the same remainder appears twice, the subarray between those indices has a sum divisible by k. This method runs in O(n) time and O(k) space, making it efficient for large inputs.
Is Subarray Sums Divisible by K asked at Google/Amazon/Meta?
This problem is a common prefix sum and hashing pattern frequently discussed in coding interviews at large tech companies such as Amazon, Google, and Meta. Variants involving prefix sums, modulo arithmetic, and subarray counting appear regularly in interview question banks.
What data structure is used in Subarray Sums Divisible by K?
The optimal solution uses a hash map (or dictionary) to store frequencies of prefix sum remainders. Combined with a running prefix sum over the array, the hash table enables constant-time lookup to count valid subarrays.
What is the time complexity of Subarray Sums Divisible by K?
The optimal solution runs in O(n) time because the array is processed once while maintaining a hash map of remainder counts. The brute force approach requires checking every subarray, which leads to O(n²) time complexity.

Ready to solve this problem?

Practice Subarray Sums Divisible by K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Number of Bad Pairs

Next

Count of Interesting Subarrays