Q30 PepCoding | Longest Subarray With Sum Divisible By K
Thu Jan 26 2023 20:11:21 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.*;
public class Main {
public static int solution(int[] arr, int k) {
//make hashmap<PSA,Index> and keep storing PSA , if (PSA - k) exists and is divisible by k store length of i - index of (psa-k)
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 = Math.max(ans , i - map.get(rem));
else
map.put(rem , i);
}
return ans;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scn.nextInt();
}
int k = scn.nextInt();
System.out.println(solution(arr, k));
}
}
content_copyCOPY
https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/hashmap-and-heaps/longest-subarray-with-sum-divisible-by-k-official/ojquestion
Comments