Subarray with no pair sum divisible by K | Java Program to find the subarray with no pair sum divisible by K ; function to find the subarray with no pair sum divisible by k ; hash table to store the remainders obtained on dividing by K ; s : starting index of the current subarray , e : ending index of the current subarray , maxs : starting index of the maximum size subarray so far , maxe : ending index of the maximum size subarray so far ; insert the first element in the set ; Removing starting elements of current subarray while there is an element in set which makes a pair with mod [ i ] such that the pair sum is divisible . ; include the current element in the current subarray the ending index of the current subarray increments by one ; compare the size of the current subarray with the maximum size so far ; Driver Code
import java . io . * ; import java . util . * ; public class GFG { static void subarrayDivisibleByK ( int [ ] arr , int n , int k ) { int [ ] mp = new int [ 1000 ] ; int s = 0 , e = 0 , maxs = 0 , maxe = 0 ; mp [ arr [ 0 ] % k ] ++ ; for ( int i = 1 ; i < n ; i ++ ) { int mod = arr [ i ] % k ; while ( mp [ k - mod ] != 0 || ( mod == 0 && mp [ mod ] != 0 ) ) { mp [ arr [ s ] % k ] -- ; s ++ ; } mp [ mod ] ++ ; e ++ ; if ( ( e - s ) > ( maxe - maxs ) ) { maxe = e ; maxs = s ; } } System . out . print ( " The ▁ maximum ▁ size ▁ is ▁ " + ( maxe - maxs + 1 ) + " and the subarray is as followsNEW_LINE"); for ( int i = maxs ; i <= maxe ; i ++ ) System . out . print ( arr [ i ] + " ▁ " ) ; } public static void main ( String args [ ] ) { int k = 3 ; int [ ] arr = { 5 , 10 , 15 , 20 , 25 } ; int n = arr . length ; subarrayDivisibleByK ( arr , n , k ) ; } }