Longest subarray with sum not divisible by X | Function to print the longest subarray with sum of elements not divisible by X ; Pref [ ] stores the prefix sum Suff [ ] stores the suffix sum ; If array element is divisibile by x ; Increase count ; If all the array elements are divisible by x ; No subarray possible ; Reverse v to calculate the suffix sum ; Calculate the suffix sum ; Reverse to original form ; Reverse the suffix sum array ; Calculate the prefix sum ; Stores the starting index of required subarray ; Stores the ending index of required subarray ; If suffix sum till i - th index is not divisible by x ; Update the answer ; If prefix sum till i - th index is not divisible by x ; Update the answer ; Print the longest subarray ; Driver code
def max_length ( N , x , v ) : NEW_LINE INDENT preff , suff = [ ] , [ ] NEW_LINE ct = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT a = v [ i ] NEW_LINE if a % x == 0 : NEW_LINE INDENT ct += 1 NEW_LINE DEDENT DEDENT if ct == N : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT v . reverse ( ) NEW_LINE suff . append ( v [ 0 ] ) NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT suff . append ( v [ i ] + suff [ i - 1 ] ) NEW_LINE DEDENT v . reverse ( ) NEW_LINE suff . reverse ( ) NEW_LINE preff . append ( v [ 0 ] ) NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT preff . append ( v [ i ] + preff [ i - 1 ] ) NEW_LINE DEDENT ans = 0 NEW_LINE lp = 0 NEW_LINE rp = N - 1 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if suff [ i ] % x != 0 and ans < N - 1 : NEW_LINE INDENT lp = i NEW_LINE rp = N - 1 NEW_LINE ans = max ( ans , N - i ) NEW_LINE DEDENT if preff [ i ] % x != 0 and ans < i + 1 : NEW_LINE INDENT lp = 0 NEW_LINE rp = i NEW_LINE ans = max ( ans , i + 1 ) NEW_LINE DEDENT DEDENT for i in range ( lp , rp + 1 ) : NEW_LINE INDENT print ( v [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT x = 3 NEW_LINE v = [ 1 , 3 , 2 , 6 ] NEW_LINE N = len ( v ) NEW_LINE max_length ( N , x , v ) NEW_LINE