Minimum removals required such that sum of remaining array modulo M is X | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findSum ( vector < int > S , int n , int x ) { vector < vector < int > > table ( n + 1 , vector < int > ( x + 1 , 0 ) ) ; for ( int i = 1 ; i <= x ; i ++ ) { table [ 0 ] [ i ] = INT_MAX - 1 ; } for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= x ; j ++ ) { if ( S [ i - 1 ] > j ) { table [ i ] [ j ] = table [ i - 1 ] [ j ] ; } else { table [ i ] [ j ] = min ( table [ i - 1 ] [ j ] , table [ i ] [ j - S [ i - 1 ] ] + 1 ) ; } } } return ( table [ n ] [ x ] > n ) ? -1 : table [ n ] [ x ] ; } void minRemovals ( vector < int > arr , int n , int m , int x ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; } int requied_Sum = 0 ; if ( sum % m < x ) requied_Sum = m + sum % m - x ; else requied_Sum = sum % m - x ; cout << findSum ( arr , n , requied_Sum ) ; } int main ( ) { vector < int > arr = { 3 , 2 , 1 , 2 } ; int n = arr . size ( ) ; int m = 4 , x = 2 ; minRemovals ( arr , n , m , x % m ) ; return 0 ; }