The Subarray Sums Divisible by K approach is a technique used to solve problems that involve finding the number of subarrays in an array whose sum is divisible by a given number (K). The approach uses the concept of “prefix sums” and “modulo operation” to efficiently find the number of such subarrays in linear time complexity.
The basic idea is to create a prefix sum array, where each element is the sum of all the elements from the start of the array to that element. Then, for each prefix sum, calculate its modulo with K, and store the result in a separate array.
The number of subarrays whose sum is divisible by K can then be found by counting the number of occurrences of each modulo result and using that to calculate the number of subarrays that have the same modulo result.
This approach can be implemented using a hash map (or similar data structure) to keep track of the count of each modulo result, and iterating through the prefix sum array to update the count of each modulo result as you go.
The time complexity of this approach is O(n), making it more efficient than other methods that have a time complexity of O(n^2).
Prefix Sum :
#include <iostream>
#include <unordered_map>
using namespace std;
int subarraysDivByK(vector<int>& A, int K) {
unordered_map<int, int> mod_count;
mod_count[0] = 1;
int prefix_sum = 0, count = 0;
for (int i = 0; i < A.size(); i++) {
prefix_sum += A[i];
int mod = (prefix_sum % K + K) % K;
if (mod_count.find(mod) != mod_count.end()) {
count += mod_count[mod];
}
mod_count[mod]++;
}
return count;
}
int main() {
vector<int> A = {4, 5, 0, -2, -3, 1};
int K = 5;
cout << subarraysDivByK(A, K) << endl;
return 0;
}
//code for Leet code C++ :
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> mod_count;
mod_count[0] = 1;
int prefix_sum = 0, count = 0;
for (int i = 0; i < nums.size(); i++) {
prefix_sum += nums[i];
int mod = (prefix_sum % k + k) % k;
if (mod_count.find(mod) != mod_count.end()) {
count += mod_count[mod];
}
mod_count[mod]++;
}
return count;
}
};Explanation of Prefix Sum :
In this example, the function subarraysDivByK() takes in two parameters: a vector of integers A representing the array and an integer K representing the number that the subarray sums should be divisible by. It uses an unordered_map to keep track of the count of each modulo result.
The variable prefix_sum keeps track of the sum of all the elements from the start of the array to the current element, and count keeps track of the number of subarrays whose sum is divisible by K.
The function iterates through the array and for each element, it calculates the prefix_sum and the modulo with K, and stores it in the mod_count map. If the mod value already exists in the map, it adds the count of that mod value to the final count. It then increments the count of that mod value in the map. Finally, it returns the count of subarrays whose sum is divisible by K.
It’s worth noting that in c++, the modulo operation % can return a negative number if the number on the left is negative. To avoid this, we add K to the result of prefix_sum % K to ensure that it will always be a positive number.
Java Solution:
Here is an example of how the Subarray Sums Divisible by K approach can be implemented in Java to solve the problem on LeetCode:
class Solution {
public int subarraysDivByK(int[] A, int K) {
int[] prefixSum = new int[A.length + 1];
for (int i = 1; i <= A.length; i++) {
prefixSum[i] = prefixSum[i - 1] + A[i - 1];
}
int[] modCount = new int[K];
int count = 0;
for (int i = 0; i <= A.length; i++) {
int mod = (prefixSum[i] % K + K) % K;
count += modCount[mod];
modCount[mod]++;
}
return count;
}
}
Explanation:
In this example, the subarraysDivByK() method takes in two parameters: an integer array A representing the array and an integer K representing the number that the subarray sums should be divisible by. It uses two arrays prefixSum and modCount to keep track of the prefix sum and the count of each modulo result respectively.
The variable count keeps track of the number of subarrays whose sum is divisible by K.
The method iterates through the array and for each element, it calculates the prefixSum and the modulo with K, and stores it in the modCount array. If the mod value already exists in the array, it adds the count of that mod value to the final count.
It then increments the count of that mod value in the array. Finally, it returns the count of subarrays whose sum is divisible by K.
You can use this implementation to solve the problem on LeetCode, and you should be able to get an O(n) time complexity and O(k) space complexity solution.
Python:
Here is an example of how the Subarray Sums Divisible by K approach can be implemented in Python to solve the problem:
def subarraysDivByK(A, K):
prefix_sum = [0] * (len(A) + 1)
for i in range(1, len(A) + 1):
prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
mod_count = [0] * K
count = 0
for i in range(len(A) + 1):
mod = (prefix_sum[i] % K + K) % K
count += mod_count[mod]
mod_count[mod] += 1
return count
JavaScript:
Here is an example of how the Subarray Sums Divisible by K approach can be implemented in JavaScript to solve the problem:
function subarraysDivByK(A, K) {
let prefixSum = new Array(A.length + 1).fill(0);
for (let i = 1; i <= A.length; i++) {
prefixSum[i] = prefixSum[i - 1] + A[i - 1];
}
let modCount = new Array(K).fill(0);
let count = 0;
for (let i = 0; i <= A.length; i++) {
let mod = (prefixSum[i] % K + K) % K;
count += modCount[mod];
modCount[mod]++;
}
return count;
}
Dart
int subarraysDivByK(List<int> A, int K) {
var prefixSum = List<int>.generate(A.length + 1, (i) => 0);
for (int i = 1; i <= A.length; i++) {
prefixSum[i] = prefixSum[i - 1] + A[i - 1];
}
var modCount = List<int>.generate(K, (i) => 0);
int count = 0;
for (int i = 0; i <= A.length; i++) {
int mod = (prefixSum[i] % K + K) % K;
count += modCount[mod];
modCount[mod]++;
}
return count;
}