Length of longest subarray whose sum is not divisible by integer K | C ++ Program to find the length of the longest subarray whose sum is not divisible by integer K ; Function to find the longest subarray with sum is not divisible by k ; left is the index of the leftmost element that is not divisible by k ; right is the index of the rightmost element that is not divisible by k ; sum of the array ; Find the element that is not multiple of k ; left = - 1 means we are finding the leftmost element that is not divisible by k ; Updating the rightmost element ; update the sum of the array up to the index i ; Check if the sum of the array is not divisible by k , then return the size of array ; All elements of array are divisible by k , then no such subarray possible so return - 1 ; length of prefix elements that can be removed ; length of suffix elements that can be removed ; Return the length of subarray after removing the elements which have lesser number of elements ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MaxSubarrayLength ( int arr [ ] , int n , int k ) { int left = -1 ; int right ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( ( arr [ i ] % k ) != 0 ) { if ( left == -1 ) { left = i ; } right = i ; } sum += arr [ i ] ; } if ( ( sum % k ) != 0 ) { return n ; } else if ( left == -1 ) { return -1 ; } else { int prefix_length = left + 1 ; int suffix_length = n - right ; return n - min ( prefix_length , suffix_length ) ; } } int main ( ) { int arr [ ] = { 6 , 3 , 12 , 15 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 3 ; cout << MaxSubarrayLength ( arr , n , K ) ; return 0 ; }