Length of smallest subarray to be removed to make sum of remaining elements divisible by K | C ++ program for the above approach ; Function to find the length of the smallest subarray to be removed such that sum of elements is divisible by K ; Stores the remainder of each arr [ i ] when divided by K ; Stores total sum of elements ; K has been added to each arr [ i ] to handle - ve integers ; Update the total sum ; Remainder when total_sum is divided by K ; If given array is already divisible by K ; Stores curr_remainder and the most recent index at which curr_remainder has occurred ; Stores required answer ; Add current element to curr_sum and take mod ; Update current remainder index ; If mod already exists in map the subarray exists ; If not possible ; Print the result ; Driver Code ; Given array arr [ ] ; Size of array ; Given K ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void removeSmallestSubarray ( int arr [ ] , int n , int k ) { int mod_arr [ n ] ; int total_sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { mod_arr [ i ] = ( arr [ i ] + k ) % k ; total_sum += arr [ i ] ; } int target_remainder = total_sum % k ; if ( target_remainder == 0 ) { cout << "0" ; return ; } unordered_map < int , int > map1 ; map1 [ 0 ] = -1 ; int curr_remainder = 0 ; int res = INT_MAX ; for ( int i = 0 ; i < n ; i ++ ) { curr_remainder = ( curr_remainder + arr [ i ] + k ) % k ; map1 [ curr_remainder ] = i ; int mod = ( curr_remainder - target_remainder + k ) % k ; if ( map1 . find ( mod ) != map1 . end ( ) ) res = min ( res , i - map1 [ mod ] ) ; } if ( res == INT_MAX res == n ) { res = -1 ; } cout << res ; } int main ( ) { int arr [ ] = { 3 , 1 , 4 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 6 ; removeSmallestSubarray ( arr , N , K ) ; return 0 ; }