Subarray Sums Divisible by K solution and explanation
Google
9 more videos on this problem
Subarray Sums Divisible by K - Leetcode 974 - PythonNeetCodeIO · 16:41 · 39K views
Subarray Sums Divisible by K | LeetCode 974 | C++, Java, PythonKnowledge Center · 16:48 · 35K views
974. Subarray Sums Divisible by K | PrefSum | Not an Easy ProblemAryan Mittal · 17:19 · 12K views
LeetCode 974. Subarray Sums Divisible by KHappy Coding · 12:48 · 7K views
Leetcode 974 Subarray Sums Divisible by K | CodingDecoded SDE sheetCoding Decoded · 10:37 · 4K views
SUBARRAY SUMS DIVISIBLE BY K | LEETCODE 974 | PYTHON SOLUTIONCracking FAANG · 16:24 · 3K views
Subarray Sums Divisible by K | LeetCode 974Jeevan Kumar - Cracckify · 6:03 · 2K views
974. Subarray Sums Divisible by K | LeetCodeDeep Tech · 11:27 · 971 views
974. Subarray Sums Divisible by K | English | MediumSimple Code - 단순코드 · 8:26 · 739 views
Subarray Sum Divisible by K – Optimal Approach Using Prefix Sum + HashMap | C++, Java, PythonRisingBrain · 20:45 · 3K views
The problem
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] <= 1042 <= 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.
def subarraysDivByK(nums, k):
modCount = {0: 1}
count = cumSum = 0
for num in nums:
cumSum += num
mod = (cumSum % k + k) % k
count += modCount.get(mod, 0)
modCount[mod] = modCount.get(mod, 0) + 1
return count
nums = [4, 5, 0, -2, -3, 1]
k = 5
print("Number of subarrays divisible by", k, ":", subarraysDivByK(nums, k))import java.util.HashMap;
public class Solution {
public int subarraysDivByK(int[] nums, int k) {
HashMap<Integer, Integer> modCount = new HashMap<>();
modCount.put(0, 1);
int count = 0, cumSum = 0;
for (int num : nums) {
cumSum += num;
int mod = ((cumSum % k) + k) % k;
count += modCount.getOrDefault(mod, 0);
modCount.put(mod, modCount.getOrDefault(mod, 0) + 1);
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {4, 5, 0, -2, -3, 1};
int k = 5;
System.out.println("Number of subarrays divisible by " + k + ": " + sol.subarraysDivByK(nums, k));
}
}#include <vector>
#include <unordered_map>
#include <iostream>
int subarraysDivByK(std::vector<int>& nums, int k) {
std::unordered_map<int, int> modCount;
modCount[0] = 1;
int count = 0, cumSum = 0;
for (int num : nums) {
cumSum += num;
int mod = ((cumSum % k) + k) % k;
count += modCount[mod];
modCount[mod]++;
}
return count;
}
int main() {
std::vector<int> nums = {4, 5, 0, -2, -3, 1};
int k = 5;
std::cout << "Number of subarrays divisible by " << k << ": " << subarraysDivByK(nums, k) << std::endl;
return 0;
}function subarraysDivByK(nums, k) {
let modCount = {0: 1};
let count = 0, cumSum = 0;
for (let num of nums) {
cumSum += num;
let mod = (cumSum % k + k) % k;
count += modCount[mod] || 0;
modCount[mod] = (modCount[mod] || 0) + 1;
}
return count;
}
const nums = [4, 5, 0, -2, -3, 1];
const k = 5;
console.log(`Number of subarrays divisible by ${k}: ${subarraysDivByK(nums, k)}`);#include <stdio.h>
#include <stdlib.h>
int subarraysDivByK(int* nums, int numsSize, int k) {
int* modCount = (int*)calloc(k, sizeof(int));
modCount[0] = 1;
int count = 0, cumSum = 0;
for (int i = 0; i < numsSize; i++) {
cumSum += nums[i];
int mod = ((cumSum % k) + k) % k;
count += modCount[mod];
modCount[mod]++;
}
free(modCount);
return count;
}
int main() {
int nums[] = {4, 5, 0, -2, -3, 1};
int k = 5;
printf("Number of subarrays divisible by %d: %d\n", k, subarraysDivByK(nums, sizeof(nums)/sizeof(int), k));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int SubarraysDivByK(int[] nums, int k) {
Dictionary<int, int> modCount = new Dictionary<int, int>();
modCount[0] = 1;
int count = 0, cumSum = 0;
foreach (var num in nums) {
cumSum += num;
int mod = ((cumSum % k) + k) % k;
count += modCount.ContainsKey(mod) ? modCount[mod] : 0;
if (modCount.ContainsKey(mod)) {
modCount[mod]++;
} else {
modCount[mod] = 1;
}
}
return count;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = new int[] {4, 5, 0, -2, -3, 1};
int k = 5;
Console.WriteLine("Number of subarrays divisible by " + k + ": " + sol.SubarraysDivByK(nums, k));
}
}In this Python solution, a dictionary is used to track the count of each remainder when computing the cumulative sum modulo k. Initially, a zero remainder is present once to facilitate counting of subarrays starting from the beginning. As each number is processed, the cumulative sum is adjusted, the current remainder is calculated, and subarray counts are updated based on previously seen remainders.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(k), due to storage of mod counts in the dictionary.
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.
def subarraysDivByK(nums, k):
count = 0
for start in range(len(nums)):
sum = 0
for end in range(start, len(nums)):
sum += nums[end]
if sum % k == 0:
count += 1
return count
nums = [4, 5, 0, -2, -3, 1]
k = 5
print("Number of subarrays divisible by", k, ":", subarraysDivByK(nums, k))public class Solution {
public int subarraysDivByK(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
int sum = 0;
for (int end = start; end < nums.length; end++) {
sum += nums[end];
if (sum % k == 0) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {4, 5, 0, -2, -3, 1};
int k = 5;
System.out.println("Number of subarrays divisible by " + k + ": " + sol.subarraysDivByK(nums, k));
}
}#include <iostream>
#include <vector>
int subarraysDivByK(std::vector<int>& nums, int k) {
int count = 0;
int n = nums.size();
for (int start = 0; start < n; start++) {
int sum = 0;
for (int end = start; end < n; end++) {
sum += nums[end];
if (sum % k == 0) {
count++;
}
}
}
return count;
}
int main() {
std::vector<int> nums = {4, 5, 0, -2, -3, 1};
int k = 5;
std::cout << "Number of subarrays divisible by " << k << ": " << subarraysDivByK(nums, k) << std::endl;
return 0;
}function subarraysDivByK(nums, k) {
let count = 0;
for (let start = 0; start < nums.length; start++) {
let sum = 0;
for (let end = start; end < nums.length; end++) {
sum += nums[end];
if (sum % k === 0) {
count++;
}
}
}
return count;
}
const nums = [4, 5, 0, -2, -3, 1];
const k = 5;
console.log(`Number of subarrays divisible by ${k}: ${subarraysDivByK(nums, k)}`);#include <stdio.h>
int subarraysDivByK(int* nums, int numsSize, int k) {
int count = 0;
for (int start = 0; start < numsSize; start++) {
int sum = 0;
for (int end = start; end < numsSize; end++) {
sum += nums[end];
if (sum % k == 0) {
count++;
}
}
}
return count;
}
int main() {
int nums[] = {4, 5, 0, -2, -3, 1};
int k = 5;
printf("Number of subarrays divisible by %d: %d\n", k, subarraysDivByK(nums, sizeof(nums)/sizeof(int), k));
return 0;
}using System;
public class Solution {
public int SubarraysDivByK(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.Length; start++) {
int sum = 0;
for (int end = start; end < nums.Length; end++) {
sum += nums[end];
if (sum % k == 0) {
count++;
}
}
}
return count;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {4, 5, 0, -2, -3, 1};
int k = 5;
Console.WriteLine("Number of subarrays divisible by " + k + ": " + sol.SubarraysDivByK(nums, k));
}
}This Python implementation uses a straightforward two-loop nested structure to evaluate each possible subarray. For each subarray, the cumulative sum is calculated, and it increments the counter if this sum is divisible by k.
Time Complexity: O(n^2), as each element can pair with others to form subarrays.
Space Complexity: O(1), because it uses only local variables for counting and summing.
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
scan be negative, we can addkto the result ofs bmod kand then take modulokagain to ensure that the value ofsis non-negative.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
function subarraysDivByK(nums: number[], k: number): number {
const cnt: { [key: number]: number } = { 0: 1 };
let s = 0;
let ans = 0;
for (const x of nums) {
s = (((s + x) % k) + k) % k;
ans += cnt[s] || 0;
cnt[s] = (cnt[s] || 0) + 1;
}
return ans;
}func subarraysDivByK(nums []int, k int) (ans int) {
cnt := map[int]int{0: 1}
s := 0
for _, x := range nums {
s = ((s+x)%k + k) % k
ans += cnt[s]
cnt[s]++
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sums with HashMap | Time Complexity: O(n), where n is the number of elements in the array. |
| Brute Force Subarray Sum | Time Complexity: O(n^2), as each element can pair with others to form subarrays. |
| Hash Table + Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Sum | O(n²) | O(1) | Useful for understanding the problem or when constraints are very small |
| Prefix Sum + HashMap | O(n) | O(k) | General case and expected interview solution for large arrays |
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.