Minimize cost of swapping set bits with unset bits in a given Binary string | C ++ program for the above approach ; Function to find the minimum cost required to swap every set bit with an unset bit ; Stores the indices of set and unset bits of the string S ; Traverse the string S ; Store the indices ; Initialize a dp table of size n1 * n2 ; Set unreachable states to INF ; Fill the dp Table according to the given recurrence relation ; Update the value of dp [ i ] [ j ] ; Return the minimum cost ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define INF  1000000000 NEW_LINE int minimumCost ( string s ) { int N = s . length ( ) ; vector < int > A , B ; for ( int i = 0 ; i < N ; i ++ ) { if ( s [ i ] == '1' ) { A . push_back ( i ) ; } else { B . push_back ( i ) ; } } int n1 = A . size ( ) ; int n2 = B . size ( ) ; int dp [ n1 + 1 ] [ n2 + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; for ( int i = 1 ; i <= n1 ; i ++ ) { dp [ i ] [ 0 ] = INF ; } for ( int i = 1 ; i <= n1 ; i ++ ) { for ( int j = 1 ; j <= n2 ; j ++ ) { dp [ i ] [ j ] = min ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j - 1 ] + abs ( A [ i - 1 ] - B [ j - 1 ] ) ) ; } } return dp [ n1 ] [ n2 ] ; } int main ( ) { string S = "1010001" ; cout << minimumCost ( S ) ; return 0 ; }