Longest subarray with sum not divisible by X | C ++ 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
#include <iostream> NEW_LINE #include <bits/stdc++.h> NEW_LINE using namespace std ; void max_length ( int N , int x , vector < int > & v ) { int i , a ; vector < int > preff , suff ; int ct = 0 ; for ( i = 0 ; i < N ; i ++ ) { a = v [ i ] ; if ( a % x == 0 ) { ct += 1 ; } } if ( ct == N ) { cout << -1 << endl ; return ; } reverse ( v . begin ( ) , v . end ( ) ) ; suff . push_back ( v [ 0 ] ) ; for ( i = 1 ; i < N ; i ++ ) { suff . push_back ( v [ i ] + suff [ i - 1 ] ) ; } reverse ( v . begin ( ) , v . end ( ) ) ; reverse ( suff . begin ( ) , suff . end ( ) ) ; preff . push_back ( v [ 0 ] ) ; for ( i = 1 ; i < N ; i ++ ) { preff . push_back ( v [ i ] + preff [ i - 1 ] ) ; } int ans = 0 ; int lp = 0 ; int rp = N - 1 ; for ( i = 0 ; i < N ; i ++ ) { if ( suff [ i ] % x != 0 && ( ans < ( N - 1 ) ) ) { lp = i ; rp = N - 1 ; ans = max ( ans , N - i ) ; } if ( preff [ i ] % x != 0 && ( ans < ( i + 1 ) ) ) { lp = 0 ; rp = i ; ans = max ( ans , i + 1 ) ; } } for ( i = lp ; i <= rp ; i ++ ) { cout << v [ i ] << " ▁ " ; } } int main ( ) { int x = 3 ; vector < int > v = { D2 : V21 , 3 , 2 , 6 } ; int N = v . size ( ) ; max_length ( N , x , v ) ; return 0 ; }