← All problems

974. Subarray Sums Divisible by K

MediumOpen on LeetCodeProblem statement

Problem Statement

974. Subarray Sums Divisible by K

Medium

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 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2:

Input: nums = [5], k = 9
Output: 0

 

Constraints:

C++

Source file
// TLE Solution: O(n^2) => using (prefixSum[j]-prefixSum[i])%k==0
// class Solution {
// public:
//     int subarraysDivByK(vector<int>& nums, int k) {
//         int sum = 0, res = 0;
//         for (int i=0; i<nums.size(); i++)
//             if(!((nums[i]=sum+=nums[i])%k))   ++res;
//         for(int i=0; i<nums.size()-1; i++)
//             for(int j=i+1; j<nums.size(); j++)
//                 if(!((nums[j]-nums[i])%k))   ++res;
//         return res;
//     }
// };

// Optimised Solution: O(n) => using prefixSum[j]%k==prefixSum[i]%k
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int prefixMod = 0, res = 0;
        vector<int> prefixModGrps(k,0); // keep count of similar remainder causing subarrays
        prefixModGrps[0]=1; // take into account solo element subarrays that are itself divisible by k
        for (int i=0; i<nums.size(); i++){
            prefixMod=(prefixMod+nums[i]%k+k)%k;
            res+=prefixModGrps[prefixMod]++;    // can be used in combo with any other prefixSum that belongs to the same mod group
        }
        return res;
    }
};