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
def subarrayDivisibleByK ( arr , n , k ) : NEW_LINE INDENT mp = [ 0 ] * 1000 NEW_LINE s = 0 ; e = 0 ; maxs = 0 ; maxe = 0 ; NEW_LINE mp [ arr [ 0 ] % k ] = mp [ arr [ 0 ] % k ] + 1 ; NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT mod = arr [ i ] % k NEW_LINE while ( mp [ k - mod ] != 0 or ( mod == 0 and mp [ mod ] != 0 ) ) : NEW_LINE INDENT mp [ arr [ s ] % k ] = mp [ arr [ s ] % k ] - 1 NEW_LINE s = s + 1 NEW_LINE DEDENT mp [ mod ] = mp [ mod ] + 1 NEW_LINE e = e + 1 NEW_LINE if ( ( e - s ) > ( maxe - maxs ) ) : NEW_LINE INDENT maxe = e NEW_LINE maxs = s NEW_LINE DEDENT DEDENT print ( " The ▁ maximum ▁ size ▁ is ▁ { } ▁ and ▁ the ▁ " . format ( ( maxe - maxs + 1 ) ) ) for i in range ( maxs , maxe + 1 ) : NEW_LINE INDENT print ( " { } ▁ " . format ( arr [ i ] ) , end = " " ) NEW_LINE DEDENT DEDENT k = 3 NEW_LINE arr = [ 5 , 10 , 15 , 20 , 25 ] NEW_LINE n = len ( arr ) NEW_LINE subarrayDivisibleByK ( arr , n , k ) NEW_LINE