Leetcode 974) Subarray Sums Divisible by K

16 Nov 2021 in Algorithms

Intuition

1. Make consecutive sequence by using runningSum and prefix Map

2. Examine if that sequence is divisible by k ,

   A bit of math here, Don’t be scared.. Nothing difficult..

   We would like to find any consecutive subarray that satisfies such that

   (runningSum - prefixSum)%k = 0 
   

3. make sure to store positive values!

My Solution

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int runningSum = 0;
        Map<Integer,Integer> m = new HashMap<>();
        int res = 0;
        m.put(0,1);
        for(int i =0;i<nums.length; i++){
            runningSum+=nums[i];
            //sum divisible by k. 
            runningSum = runningSum%k;

            if(runningSum <0){
                runningSum +=k;
            }

            if(m.containsKey(runningSum)){
                res+=m.get(runningSum);
                m.put(runningSum,m.get(runningSum)+1);
            }else{
                m.put(runningSum,1);
            }
        }
        return res;

    }
}

Other Solution

• Using an array which stores counts for all modular values prior to current sum.

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int[] mods = new int[k];
        mods[0] = 1;
        int sum = 0;
        int temp = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            temp = sum % k;
            if (temp < 0) {
                temp += k;
            }
            count += mods[temp];
            mods[temp]+=1;
        }
        return count;

    }
}