mediumHashingPattern: Prefix Sum + Hash Map
Count Divisible Subarrays Solution
Problem Statement
Given an array of integers `arr` and an integer `k`, count the number of contiguous subarrays where the sum of elements is divisible by `k`.
Examples
Example 1:
Input:{"nums":[4,5,0,-2,-3,1],"k":5}
Output:7
Explanation: The subarrays with sums divisible by 5 are: [4, 5], [5], [0], [-2, -3, 1], [4, 5, 0, -2, -3, 1], [5, 0, -2, -3, 1], [0, -2, -3, 1]
Constraints
- 1 <= n <= 3 * 10^4
- 2 <= k <= 10^4
- -10^4 <= arr[i] <= 10^4
Time: O(N) Space: O(K)
Calculate running sum. Get remainder (sum % k). Handle negative remainders. Use HashMap to store counts of each remainder seen so far. If we see a remainder again, add its previous count to total. Time O(N), Space O(K).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.