Subarray Sums Divisible by K - 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: If nums = [4,5,0,-2,-3,1] and k = 5, the subarrays with sums divisible by 5 are: [5] (sum=5), [5,0] (sum=5), [5,0,-2,-3] (sum=0), [0] (sum=0), [-2,-3] (sum=-5), and [4,5,0,-2,-3,1] (sum=5). Answer is 7.
Input & Output
Example 1 — Basic Case
$
Input:
nums = [4,5,0,-2,-3,1], k = 5
›
Output:
7
💡 Note:
The subarrays with sums divisible by 5 are: [5] (sum=5), [5,0] (sum=5), [5,0,-2,-3] (sum=0), [0] (sum=0), [-2,-3] (sum=-5), [4,5,0,-2,-3,1] (sum=5), and one more subarray for a total of 7.
Example 2 — Small Array
$
Input:
nums = [5], k = 9
›
Output:
0
💡 Note:
The only subarray is [5] with sum 5, which is not divisible by 9.
Example 3 — Multiple Divisible
$
Input:
nums = [2,4,3], k = 6
›
Output:
2
💡 Note:
Subarrays with sums divisible by 6: [2,4] (sum=6) and [2,4,3] (sum=9 → not divisible). Actually [2,4] (sum=6) and the full array [2,4,3] would be sum=9 which is not divisible by 6. Only [2,4] works, so answer is 1. Wait, let me recalculate: [2,4] has sum=6 (divisible), and we need to check all subarrays systematically.
Constraints
- 1 ≤ nums.length ≤ 3 × 104
- -104 ≤ nums[i] ≤ 104
- 2 ≤ k ≤ 104
Visualization
Tap to expand
Understanding the Visualization
1
Input
Array [4,5,0,-2,-3,1] and k=5
2
Process
Find all contiguous subarrays with sum % k = 0
3
Output
Count of valid subarrays: 7
Key Takeaway
🎯 Key Insight: Use prefix sum remainders - same remainder means the subarray between has sum divisible by k
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code