hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Subarray Sums Divisible by K
Problem : 974. Subarray Sums Divisible by K
Problem Link : leetcode.com/problems/subarray-sums-divisible-by-k/
Companies Asked : Twilio, Amazon, Facebook, Snapchat
Approach:
Given an array. We need to find the number of subarrays whose sum is divisible by K.
Well, in O(N^2) complexity, how can we solve it?
We will be starting from an index, i. We will keep moving to any j where, j > i.
Take the sum from i to j.
If the sum is divisible by K, then increase the subarray count by 1.
Return the count.
The inner loop of calculating the sum from i to j can be found from prefix sum, that is prefixSum[j] - prefixSum[i-1].
And, (prefixSum[j] - prefixSum[i-1]) % K = 0.
It can be written as prefixSum[j]%K = prefixSum[i-1]%K.
That means when I am at index j, there might have some (i - 1) whose prefix sum is the same as j.
Which reflects the count of prefix sum modulo K will be the total amount of subarray sum modulo K.
However, there is one more catch. 0 is always divisible K and it will return 0 as its remainder value. Now when for sure it is possible to have a 0? If we have nothing in our hands. That means the count of 0 will always be set to 1.
We will return the total count at the end.
Take care of the modulo of the negative sum.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(1)
Code [C++]
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int>frequency;
int n = nums.size(), ans = 0;
frequency[0]++;
for(int i=0; i<n; i++){
nums[i] = ((i - 1) < 0 ? 0 : nums[i-1]) + nums[i];
int modValue = (nums[i]%k < 0) ? (nums[i]%k) + k : nums[i]%k;
ans += frequency[modValue];
frequency[modValue]++;
}
return ans;
}
};