Length of smallest subarray to be removed to make sum of remaining elements divisible by K | Python3 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 ; Given array arr [ ] ; Size of array ; Given K ; Function Call
import sys NEW_LINE def removeSmallestSubarray ( arr , n , k ) : NEW_LINE INDENT mod_arr = [ 0 ] * n NEW_LINE total_sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT mod_arr [ i ] = ( arr [ i ] + k ) % k NEW_LINE total_sum += arr [ i ] NEW_LINE DEDENT target_remainder = total_sum % k NEW_LINE if ( target_remainder == 0 ) : NEW_LINE INDENT print ( "0" ) NEW_LINE return NEW_LINE DEDENT map1 = { } NEW_LINE map1 [ 0 ] = - 1 NEW_LINE curr_remainder = 0 NEW_LINE res = sys . maxsize NEW_LINE for i in range ( n ) : NEW_LINE INDENT curr_remainder = ( curr_remainder + arr [ i ] + k ) % k NEW_LINE map1 [ curr_remainder ] = i NEW_LINE mod = ( curr_remainder - target_remainder + k ) % k NEW_LINE if ( mod in map1 . keys ( ) ) : NEW_LINE INDENT res = min ( res , i - map1 [ mod ] ) NEW_LINE DEDENT DEDENT if ( res == sys . maxsize or res == n ) : NEW_LINE INDENT res = - 1 NEW_LINE DEDENT print ( res ) NEW_LINE DEDENT arr = [ 3 , 1 , 4 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE K = 6 NEW_LINE removeSmallestSubarray ( arr , N , K ) NEW_LINE