Minimum removals required such that sum of remaining array modulo M is X | Python3 program for the above approach ; Function to find the minimum elements having sum x ; Initialize dp table ; Pre - compute subproblems ; If mod is smaller than element ; Minimum elements with sum j upto index i ; Return answer ; Function to find minimum number of removals to make sum % M in remaining array is equal to X ; Sum of all elements ; Sum to be removed ; Print answer ; Driver Code ; Given array ; Given size ; Given mod and x ; Function call
import sys NEW_LINE def findSum ( S , n , x ) : NEW_LINE INDENT table = [ [ 0 for x in range ( x + 1 ) ] for y in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , x + 1 ) : NEW_LINE INDENT table [ 0 ] [ i ] = sys . maxsize - 1 NEW_LINE DEDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , x + 1 ) : NEW_LINE INDENT if ( S [ i - 1 ] > j ) : NEW_LINE INDENT table [ i ] [ j ] = table [ i - 1 ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT table [ i ] [ j ] = min ( table [ i - 1 ] [ j ] , table [ i ] [ j - S [ i - 1 ] ] + 1 ) NEW_LINE DEDENT DEDENT DEDENT if ( table [ n ] [ x ] > n ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return table [ n ] [ x ] NEW_LINE DEDENT def minRemovals ( arr , n , m , x ) : NEW_LINE INDENT sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum += arr [ i ] NEW_LINE DEDENT requied_Sum = 0 NEW_LINE if ( sum % m < x ) : NEW_LINE INDENT requied_Sum = m + sum % m - x NEW_LINE DEDENT else : NEW_LINE INDENT requied_Sum = sum % m - x NEW_LINE DEDENT print ( findSum ( arr , n , requied_Sum ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 2 , 1 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE m = 4 NEW_LINE x = 2 NEW_LINE minRemovals ( arr , n , m , x % m ) NEW_LINE DEDENT