# Method - 1
public static int subArrayCount(ArrayList < Integer > arr, int k) { //tc = O(N^2), sc = O() - prefix sum array approach
int prefix[] = new int[arr.size()];
int count = 0;
prefix[0] = arr.get(0);
for(int i=1; i<arr.size(); i++){
prefix[i] = prefix[i-1] + arr.get(i);
}
for(int start=0; start<arr.size(); start++){
int sum = 0;
for(int end=start; end<arr.size(); end++){
sum = start == 0? prefix[end] : prefix[end] - prefix[start-1];
if(sum%k == 0){
count++;
}
}
}
return count;
}
# Method - 2
public static int subArrayCount2(ArrayList<Integer> arr, int k){//tcc = O(N^2), sc = O(1)
int count = 0;
for(int i=0; i<arr.size(); i++){
int currSum = 0;
for(int j=i; j<arr.size(); j++){
currSum += arr.get(j);
if(currSum % k == 0){
count++;
}
}
}
return count;
}
# Method - 3 // passed all the test cases at leetcode and GFG but didn't pass at Coding ninjas - idk why ?
public static int subArrayCount3(ArrayList < Integer > arr, int k) {//tc = O(N), sc = (N)4
//it's a mathematics related question
//hint :- count of subarrays will be the frequncy of remainder in hashmap - to know why refer to anu youtube solution because it's
//not possible here to exxplain in words.
//take hashmap and store remainder and it's frequency.
//explaination - iterate through the arraylist and do sum and get the remainder by dividing sum by k (given) and iterate till
//you get the same remiander again in this same process and count will be the frequency of that remainder then increase
//the frequency of that remainder in hashmap.
HashMap<Integer,Integer> mapp = new HashMap<>(); //key - remiander, value - frequency
mapp.put(0,1); //at first position the sum is zero therefore the remiander will also be zero and it's frequency will also be zero
int currSum = 0; //initilise the sum with zero
int count = 0; //count of subarrays
for(int i=0; i<arr.size(); i++){
currSum += arr.get(i);
int remainder = currSum%k;
if(remainder < 0){//in case if remiander is negative then add k to that remainder in order to make it positive. why ? refer to any yt video
remainder += k;
}
if(mapp.containsKey(remainder)){//if map conatins remainder
count += mapp.get(remainder); //then add it's frew to count because as we know it it the ans
mapp.put(remainder,mapp.get(remainder)+1); //and increase the freq of that remainder in hashmap
}else{
mapp.put(remainder,1);//if map do not contains remainder then add it to map with freq 1 as it has occured first time
}
}
return count;
}