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


  • Approach:

    1. Given an array. We need to find the number of subarrays whose sum is divisible by K.

    2. 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.

    3. The inner loop of calculating the sum from i to j can be found from prefix sum, that is prefixSum[j] - prefixSum[i-1].

    4. And, (prefixSum[j] - prefixSum[i-1]) % K = 0.

    5. It can be written as prefixSum[j]%K = prefixSum[i-1]%K.

    6. That means when I am at index j, there might have some (i - 1) whose prefix sum is the same as j.

    7. Which reflects the count of prefix sum modulo K will be the total amount of subarray sum modulo K.

    8. 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.

    9. We will return the total count at the end.

    10. 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;

}

};