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.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 3 * 104
	-104 &lt;= nums[i] &lt;= 104
	2 &lt;= k &lt;= 104


class Solution:
    def subarraysDivByK(self, nums, k):
        n = len(nums)
        prefix_mod = 0
        result = 0

        # There are k mod groups 0...k-1.
        mod_groups = [0] * k
        mod_groups[0] = 1

        for num in nums:
            # Take modulo twice to avoid negative remainders.
            prefix_mod = (prefix_mod + num % k + k) % k
            # Add the count of subarrays that have the same remainder as the current
            # one to cancel out the remainders.
            result += mod_groups[prefix_mod]
            mod_groups[prefix_mod] += 1

        return result
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int count = 0;
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum +=nums[i];
            int rem =sum%k;
            if(rem <0){
                rem = rem+k; // -4%3 == -1 and 2 both bec -4 = 3(-1) +(-1) = 3(-2) + 2
            }
            
            if(rem==0){
                count++;
            }
            if(map.containsKey(rem)){
                count+=map.get(rem);
            }
            
            map.put(rem,map.getOrDefault(rem,0)+1);
        }
        return count;
    }
}
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        // take an ans variable
        int ans = 0;
        // initialize a map of int, int and insert {0,1} as 0 occurs first time for sum
        unordered_map<int, int> mapp;
        mapp.insert({0,1});
        // initialize presum = 0 and remainder rem = 0 which will be used in further calculations
        int presum = 0;

        int rem = 0;

        // Logic
        /*
            1. We will traverse the entire given array/vector.
            2. While traversing we will add the element in our presum, i.e presum += nums[i] .
            3. Now we will do the % of presum and k and store it in rem that we have created.
            4. We need to take care of negative value of rem. If it is < 0, then we will add k to the remainder to make it positive.
            5. Now we will check if rem already exist in the map. If it exist then we will add it's frequency to ans variable
             and then increment rem's value in map, i.e. mapp[rem]++, else we will add it in the map.
            6. At last we will return ans.
        */

        for(int i=0; i<nums.size(); i++)
        {
            presum += nums[i];
            rem = presum % k;
            if(rem < 0)
                rem += k;

            if(mapp.find(rem) != mapp.end())
            {
                ans += mapp[rem];
                mapp[rem]++;
            }
            else
            {
                mapp.insert({rem,1});
            }
        }
        return ans;
    }
};
var subarraysDivByK = function(nums, k) {
    let count = 0;
    let map = new Map();
    map.set(0, 1)
    let sum = 0;
    for(let i=0; i<nums.length; i++){
        sum += nums[i];
        let rem = sum%k;
        if(rem<0) rem += k;
        if(map.has(rem)){
            count += map.get(rem)
            map.set(rem, map.get(rem)+1)
        }else{
            map.set(rem, 1)
        }
    }
    return count
};
Subarray Sums Divisible by K