Log inSign up
mediumLeetCodeNot Started

Subarray Sums Divisible by K

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 · Standard Example with Positives and Negatives:

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

Example 2 · Single Negative Number:

Input: nums = [5], k = 9
Output: 0
Explanation: No subarray sum is divisible by 9.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Prefix Sum technique
  • Modulo Congruence — (A - B) % K == 0 <=> A % K == B % K
  • Handling negative modulo in programming languages

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply remainder congruence to subarray sum problems.
  • Correctly normalize negative modulo in C++, Java, JS, and Python.
  • Initialize base state count[0] = 1 to capture subarrays starting at index 0.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Initialize count array of size k with count[0] = 1.
  • Compute normalized rem = ((runningSum % k) + k) % k.
  • ans += count[rem]; count[rem]++;

Connected Patterns:

Subarray Sum Equals K (LeetCode 560)Continuous Subarray Sum (LeetCode 523)

1. Check All Subarrays (Brute Force)

Intuition

Run two nested loops from start 0 to n-1 and end start to n-1. Accumulate elements in sum. If sum % k == 0 (with proper handling for negative numbers), increment the counter.

When to apply: Use to understand the baseline problem statement before optimizing.

Brute Force Subarray Inspection Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 5, 0, -2, -3, 1]
Current operationSTEP 1 OF 6
Array: [4, 5, 0, -2, -3, 1], k = 5
Visual state
Values and pointers at this exact step
array
S
4
5
0
-2
-3
1
0
↑ Start
1
2
3
4
5
Variables at this step
start
0
count
0
Check / comparison
Start at index 0.
Decision / next transition
Begin testing subarrays starting at index 0.
Why this step matters

Array: [4, 5, 0, -2, -3, 1], k = 5. Outer start = 0.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int subarraysDivByK(int[] nums, int k) {
4 int count = 0;
5 for (int i = 0; i < nums.length; i++) {
6 int sum = 0;
7 for (int j = i; j < nums.length; j++) {
8 sum += nums[j];
9 if (sum % k == 0) count++;
10 }
11 }
12 return count;
13 }
14 }
15
16 public static void main(String[] args) {
17 Solution sol = new Solution();
18 int[] nums = {4, 5, 0, -2, -3, 1};
19 int k = 5;
20 System.out.println("Subarrays divisible: " + sol.subarraysDivByK(nums, k));
21 }
22}

Time & Space Complexity

  • Time complexity: O(n^2) — Nested loops examine all n*(n+1)/2 subarrays with O(1) accumulation.
  • Space complexity: O(1) — Only scalar counters are used.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Prefix Sum Array with Remainder Tracking

Intuition

If two prefix sums prefix[j] and prefix[i] have the same remainder when divided by k, then (prefix[j] - prefix[i]) is a multiple of k.

When to apply: Use to understand prefix sum modular arithmetic.

Prefix Remainder Congruence Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 5, 0, -2, -3, 1]
Current operationSTEP 1 OF 6
Precompute prefix sum array: [0, 4, 9, 9, 7, 4, 5]
Visual state
Values and pointers at this exact step
array
S
4
5
0
-2
-3
1
0
↑ Init
1
2
3
4
5
Variables at this step
prefix
[0,4,9,9,7,4,5]
rems
[0,4,4,4,2,4,0]
Check / comparison
Remainders mod 5: [0, 4, 4, 4, 2, 4, 0].
Decision / next transition
Any two indices sharing remainder produce a valid subarray.
Why this step matters

Precompute prefix sum array: [0, 4, 9, 9, 7, 4, 5].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int subarraysDivByK(int[] nums, int k) {
4 int n = nums.length;
5 int[] prefix = new int[n + 1];
6 for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
7
8 int count = 0;
9 for (int i = 0; i <= n; i++) {
10 for (int j = i + 1; j <= n; j++) {
11 int diff = prefix[j] - prefix[i];
12 if (diff % k == 0) count++;
13 }
14 }
15 return count;
16 }
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 int[] nums = {4, 5, 0, -2, -3, 1};
22 int k = 5;
23 System.out.println("Subarrays divisible: " + sol.subarraysDivByK(nums, k));
24 }
25}

Time & Space Complexity

  • Time complexity: O(n^2) — O(n) to compute prefix sums, O(n2) to test all pair combinations.
  • Space complexity: O(n) — O(n) auxiliary space to store prefix sums.

3. Single-Pass Prefix Modulo Frequency Array (Optimal & Standard)

Intuition

1. Maintain running prefix sum. 2. Normalize remainder: rem = ((prefix % k) + k) % k. 3. Add count[rem] to answer, because every previous occurrence of rem forms a divisible subarray ending at the current position. 4. Increment count[rem].

When to apply: Use as the optimal standard for any subarray divisibility question.

Single-Pass Remainder Frequency Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 5, 0, -2, -3, 1]
Current operationSTEP 1 OF 6
Initialize count array of size k=5
Visual state
Values and pointers at this exact step
pointers
S
4
5
0
-2
-3
1
0
↑ i=0
1
2
3
4
5
Variables at this step
count
[1,0,0,0,0]
ans
0
sum
0
Check / comparison
Base case: count[0] = 1.
Decision / next transition
Initialize remainder table.
Why this step matters

Initialize count array of size k=5. count[0] = 1 (representing empty prefix with sum 0). ans = 0, sum = 0.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int subarraysDivByK(int[] nums, int k) {
4 int[] count = new int[k];
5 count[0] = 1;
6 int prefixSum = 0, result = 0;
7
8 for (int num : nums) {
9 prefixSum += num;
10 int rem = ((prefixSum % k) + k) % k;
11 result += count[rem];
12 count[rem]++;
13 }
14 return result;
15 }
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 int[] nums = {4, 5, 0, -2, -3, 1};
21 int k = 5;
22 System.out.println("Subarrays divisible: " + sol.subarraysDivByK(nums, k));
23 }
24}

Time & Space Complexity

  • Time complexity: O(n) — Single pass of n elements with O(1) array lookups.
  • Space complexity: O(k) — Array of size k to store remainder frequencies.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Nested LoopsO(N^2)O(1)Evaluate sum of all subarrays (i..j) and test sum % k == 0.Inspects all O(N2) subarrays.
2.Better — Prefix Sums Array with Modulo ScanO(N^2)O(N)Precompute prefix sums and compare all pairs (i, j) for equal remainder.Pairwise comparisons.
3.Optimal — Prefix Modulo Frequency ArrayOptimalO(N)O(K)Track frequency of each remainder [0..k-1] in a single pass.None; industry gold standard.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Subarray Sums Divisible by K?

2.Why is the brute force approach suboptimal for large inputs in Subarray Sums Divisible by K?

3.Which data structure or technique enables the optimal solution for Subarray Sums Divisible by K?

Back to DSA Sheet