Q31 Subarray Sums Divisible by K - LeetCode
Thu Jan 26 2023 21:21:50 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
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;
}
}
content_copyCOPY
https://leetcode.com/problems/subarray-sums-divisible-by-k/
Comments