Longest subarray with sum not divisible by X | Java program to implement the above approach ; 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
import java . util . * ; class GFG { static void max_length ( int N , int x , int [ ] v ) { int i , a ; List < Integer > preff = new Vector < Integer > ( ) ; List < Integer > suff = new Vector < Integer > ( ) ; int ct = 0 ; for ( i = 0 ; i < N ; i ++ ) { a = v [ i ] ; if ( a % x == 0 ) { ct += 1 ; } } if ( ct == N ) { System . out . print ( - 1 + "NEW_LINE"); return ; } v = reverse ( v ) ; suff . add ( v [ 0 ] ) ; for ( i = 1 ; i < N ; i ++ ) { suff . add ( v [ i ] + suff . get ( i - 1 ) ) ; } v = reverse ( v ) ; Collections . reverse ( suff ) ; preff . add ( v [ 0 ] ) ; for ( i = 1 ; i < N ; i ++ ) { preff . add ( v [ i ] + preff . get ( i - 1 ) ) ; } int ans = 0 ; int lp = 0 ; int rp = N - 1 ; for ( i = 0 ; i < N ; i ++ ) { if ( suff . get ( i ) % x != 0 && ( ans < ( N - 1 ) ) ) { lp = i ; rp = N - 1 ; ans = Math . max ( ans , N - i ) ; } if ( preff . get ( i ) % x != 0 && ( ans < ( i + 1 ) ) ) { lp = 0 ; rp = i ; ans = Math . max ( ans , i + 1 ) ; } } for ( i = lp ; i <= rp ; i ++ ) { System . out . print ( v [ i ] + " ▁ " ) ; } } static int [ ] reverse ( int a [ ] ) { int i , n = a . length , t ; for ( i = 0 ; i < n / 2 ; i ++ ) { t = a [ i ] ; a [ i ] = a [ n - i - 1 ] ; a [ n - i - 1 ] = t ; } return a ; } public static void main ( String [ ] args ) { int x = 3 ; int [ ] v = { 1 , 3 , 2 , 6 } ; int N = v . length ; max_length ( N , x , v ) ; } }