class Solution { public int subarraysDivByK(int[] arr, int k) { //make a HM<remainder,frequency of remainder > , traverse and make PSA and keep storing remainders //if any remainder repeats then subarray between them will be divisible of k // add frequency of rem to answer and then add rem itself HashMap<Integer, Integer> map = new HashMap<>(); int psa = 0 , ans = 0 ; map.put(0 , 1); for(int i =0 ;i < arr.length ; i++){ int val = arr[i]; psa += val; //find remainder int rem = psa%k; //if remainder comes out to be -ve add k if(rem < 0) rem += k; if(map.containsKey(rem)){ ans += map.get(rem); } map.put(rem , map.getOrDefault(rem,0)+1); } return ans; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter