Minimize cost of swapping set bits with unset bits in a given Binary string
Given a binary string S of size N, the task is to find the minimum cost by swapping every set bit with an unset bit such that the cost of swapping pairs of bits at indices i and j is abs(j β i).
Note: A swapped bit canβt be swapped twice and the count of set bit in the given binary string is at most N/2.
Examples:
Input: S = β1010001β
Output: 3
Explanation:
Following the swapping of characters required:
- Swap characters at indices (0, 1) modifies the string to β0110001β and the cost of this operation is |1 β 0| = 1.
- Swap characters at indices (2, 3) modifies the string to β0101001β and the cost of this operation is |2 β 1| = 1.
- Swap characters at indices (6, 7) modifies the string to β0101010β and the cost of this operation is |7 β 6| = 1.
After the above operations, all the set bits is replaced with unset bits and the total cost of operations is 1 + 1 + 1 = 3.
Input: S = β1100β
Output: 4
Approach: The given problem can be solved using Dynamic Programming by storing the indices of set and unset bits in two auxiliary arrays, say A[] and B[], and then find the sum of the difference between array elements A[] with any element of the array B[]. Follow the steps below to solve the given problem:
- Initialize two arrays, say A[] and B[], and store the indices of set and unset bits in it.
- Initialize a 2D array, dp[][] of dimensions K*(N β K) where K is the count of set bit in S such thatdp[i][j] stores the minimum cost of swapping the ith array element A[] with the jth array element B[].
- Now, for each state there are two choices:
- Swap the ith array element A[] till the (j β 1)th array element B[] as dp[i][j] = dp[i][j β 1].
- Swap the (i β 1)th array element A[] till the (j β 1)th array element B[] and the ith array element A[] with jth array element B[] and this state can be calculated as dp[i][j] = dp[i β 1][j β 1] + abs(A[i] β B[i]).
- Now, choose the minimum of the above two choices to find the current state as:
dp[i][j] = min(dp[i][j-1], dp[i-1][j-1] + abs(A[i] β B[j]))
- After completing the above steps, print the value of dp[K][N β K] as the resultant minimum number of operations.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define INF 1000000000 // Function to find the minimum cost // required to swap every set bit with // an unset bit int minimumCost(string s) { int N = s.length(); // Stores the indices of set and // unset bits of the string S vector< int > A, B; // Traverse the string S for ( int i = 0; i < N; i++) { // Store the indices if (s[i] == '1' ) { A.push_back(i); } else { B.push_back(i); } } int n1 = A.size(); int n2 = B.size(); // Initialize a dp table of size // n1*n2 int dp[n1 + 1][n2 + 1]; // Initialize all states to 0 memset (dp, 0, sizeof (dp)); // Set unreachable states to INF for ( int i = 1; i <= n1; i++) { dp[i][0] = INF; } // Fill the dp Table according to // the given recurrence relation for ( int i = 1; i <= n1; i++) { for ( int j = 1; j <= n2; j++) { // Update the value of // dp[i][j] dp[i][j] = min( dp[i][j - 1], dp[i - 1][j - 1] + abs (A[i - 1] - B[j - 1])); } } // Return the minimum cost return dp[n1][n2]; } // Driver Code int main() { string S = "1010001" ; cout << minimumCost(S); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ static final int INF = 1000000000 ; // Function to find the minimum cost // required to swap every set bit with // an unset bit static int minimumCost(String s) { int N = s.length(); // Stores the indices of set and // unset bits of the String S Vector<Integer> A = new Vector<Integer>(); Vector<Integer> B = new Vector<Integer>(); // Traverse the String S for ( int i = 0 ; i < N; i++) { // Store the indices if (s.charAt(i) == '1' ) { A.add(i); } else { B.add(i); } } int n1 = A.size(); int n2 = B.size(); // Initialize a dp table of size // n1*n2 int [][]dp = new int [n1 + 1 ][n2 + 1 ]; // Set unreachable states to INF for ( int i = 1 ; i <= n1; i++) { dp[i][ 0 ] = INF; } // Fill the dp Table according to // the given recurrence relation for ( int i = 1 ; i <= n1; i++) { for ( int j = 1 ; j <= n2; j++) { // Update the value of // dp[i][j] dp[i][j] = Math.min( dp[i][j - 1 ], dp[i - 1 ][j - 1 ] + Math.abs(A.get(i - 1 ) - B.get(j - 1 ))); } } // Return the minimum cost return dp[n1][n2]; } // Driver Code public static void main(String[] args) { String S = "1010001" ; System.out.print(minimumCost(S)); } } // This code is contributed by shikhasingrajput |
Python3
# Python program for the above approach INF = 1000000000 # Function to find the minimum cost # required to swap every set bit with # an unset bit def minimumCost(s): N = len (s) # Stores the indices of set and # unset bits of the string S A = [] B = [] # Traverse the string S for i in range ( 0 , N): # Store the indices if (s[i] = = "1" ): A.append(i) else : B.append(i) n1 = len (A) n2 = len (B) # Initialize a dp table of size # n1*n2 dp = [[ 0 for i in range (n2 + 1 )] for j in range (n1 + 1 )] # Set unreachable states to INF for i in range ( 1 , n1 + 1 ): dp[i][ 0 ] = INF # Fill the dp Table according to # the given recurrence relation for i in range ( 1 , n1 + 1 ): for j in range ( 1 , n2 + 1 ): # Update the value of # dp[i][j] dp[i][j] = min ( dp[i][j - 1 ], dp[i - 1 ][j - 1 ] + abs (A[i - 1 ] - B[j - 1 ]) ) # Return the minimum cost return dp[n1][n2] # Driver Code S = "1010001" print (minimumCost(S)) # This code is contributed by _saurabh_jaiswal. |
C#
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; public class Program { // Function to find the minimum cost // required to swap every set bit with // an unset bit static int minimumCost( string s) { int INF = 1000000000; int N = s.Length; // Stores the indices of set and // unset bits of the string S List< int > A = new List< int >(); List< int > B = new List< int >(); // Traverse the string S for ( int i = 0; i < N; i++) { // Store the indices if (s[i] == '1' ) { A.Add(i); } else { B.Add(i); } } int n1 = A.Count; int n2 = B.Count; // Initialize a dp table of size // n1*n2 int [,]dp = new int [n1 + 1,n2 + 1]; // Set unreachable states to INF for ( int i = 1; i <= n1; i++) { dp[i,0] = INF; } // Fill the dp Table according to // the given recurrence relation for ( int i = 1; i <= n1; i++) { for ( int j = 1; j <= n2; j++) { // Update the value of // dp[i][j] dp[i,j] = Math.Min( dp[i,j - 1], dp[i - 1,j - 1] + Math.Abs(A[i - 1] - B[j - 1])); } } // Return the minimum cost return dp[n1,n2]; } public static void Main() { string S = "1010001" ; Console.Write(minimumCost(S)); } } // This code is contributed by rutvik_56. |
Javascript
<script> // Javascript program for the above approach let INF = 1000000000; // Function to find the minimum cost // required to swap every set bit with // an unset bit function minimumCost(s) { let N = s.length; // Stores the indices of set and // unset bits of the string S let A = [], B = []; // Traverse the string S for (let i = 0; i < N; i++) { // Store the indices if (s[i] == "1" ) { A.push(i); } else { B.push(i); } } let n1 = A.length; let n2 = B.length; // Initialize a dp table of size // n1*n2 let dp = new Array(n1 + 1).fill(0).map(() => new Array(n2 + 1).fill(0)); // Set unreachable states to INF for (let i = 1; i <= n1; i++) { dp[i][0] = INF; } // Fill the dp Table according to // the given recurrence relation for (let i = 1; i <= n1; i++) { for (let j = 1; j <= n2; j++) { // Update the value of // dp[i][j] dp[i][j] = Math.min( dp[i][j - 1], dp[i - 1][j - 1] + Math.abs(A[i - 1] - B[j - 1]) ); } } // Return the minimum cost return dp[n1][n2]; } // Driver Code let S = "1010001" ; document.write(minimumCost(S)); // This code is contributed by gfgking. </script> |
3
Time Complexity: O(K*(N β K)) where K is the count of set bit in S.
Auxiliary Space: O(K*(N β K))
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size n+1 and initialize it with 0.
- Set a base case by initializing the values of DP .
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- At last return and print the final answer stored in dp[n].
Implementation:
C++
#include <bits/stdc++.h> using namespace std; #define INF 1000000000 // Function to find the minimum cost // required to swap every set bit with // an unset bit int minimumCost(string s) { int n1 = 0, n2 = 0; for ( char c : s) { if (c == '1' ) n1++; else n2++; } // Initialize a dp table of size // n1*n2 int dp[n1 + 1]; // Initialize all states to 0 memset (dp, 0, sizeof (dp)); // Set unreachable states to INF for ( int i = 1; i <= n1; i++) { dp[i] = INF; } // Fill the dp Table according to // the given recurrence relation for ( char c : s) { for ( int i = n1; i >= 1; i--) { if (c == '0' ) dp[i] = min(dp[i], dp[i - 1] + n2 - i + 1); else dp[i] = min(dp[i], dp[i - 1] + i - 1); } } // Return the minimum cost return dp[n1]; } // Driver Code int main() { string S = "1010001" ; cout << minimumCost(S); return 0; } |
Java
import java.util.Arrays; public class MinimumCost { static int INF = 1000000000 ; // Function to find the minimum cost // required to swap every set bit with // an unset bit static int minimumCost(String s) { int n1 = 0 , n2 = 0 ; for ( char c : s.toCharArray()) { if (c == '1' ) { n1++; } else { n2++; } } // Initialize a dp table of size // n1*n2 int [] dp = new int [n1 + 1 ]; // Initialize all states to 0 Arrays.fill(dp, 0 ); // Set unreachable states to INF for ( int i = 1 ; i <= n1; i++) { dp[i] = INF; } // Fill the dp Table according to // the given recurrence relation for ( char c : s.toCharArray()) { for ( int i = n1; i >= 1 ; i--) { if (c == '0' ) { dp[i] = Math.min(dp[i], dp[i - 1 ] + n2 - i + 1 ); } else { dp[i] = Math.min(dp[i], dp[i - 1 ] + i - 1 ); } } } // Return the minimum cost return dp[n1]; } // Driver Code public static void main(String[] args) { String S = "1010001" ; System.out.println(minimumCost(S)); } } |
Python
INF = 1000000000 # Function to find the minimum cost # required to swap every set bit with an unset bit def minimumCost(s): n1 = s.count( '1' ) n2 = len (s) - n1 # Initialize a dp table of size n1*n2 dp = [ 0 ] * (n1 + 1 ) # Set unreachable states to INF for i in range ( 1 , n1 + 1 ): dp[i] = INF # Fill the dp Table according # to the given recurrence relation for c in s: for i in range (n1, 0 , - 1 ): if c = = '0' : dp[i] = min (dp[i], dp[i - 1 ] + n2 - i + 1 ) else : dp[i] = min (dp[i], dp[i - 1 ] + i - 1 ) # Return the minimum cost return dp[n1] # Driver Code if __name__ = = "__main__" : S = "1010001" print (minimumCost(S)) |
C#
using System; namespace MinimumCostToSwapBits { class Program { static int INF = 1000000000; static int MinimumCost( string s) { int n1 = 0, n2 = 0; foreach ( char c in s) { if (c == '1' ) n1++; else n2++; } int [] dp = new int [n1 + 1]; Array.Fill(dp, 0); for ( int i = 1; i <= n1; i++) { dp[i] = INF; } foreach ( char c in s) { for ( int i = n1; i >= 1; i--) { if (c == '0' ) dp[i] = Math.Min(dp[i], dp[i - 1] + n2 - i + 1); else dp[i] = Math.Min(dp[i], dp[i - 1] + i - 1); } } return dp[n1]; } static void Main( string [] args) { string S = "1010001" ; Console.WriteLine(MinimumCost(S)); } } } |
Javascript
function minimumCost(s) { const INF = 1000000000; let n1 = 0, n2 = 0; for (let i = 0; i < s.length; i++) { if (s.charAt(i) == '1' ) n1++; else n2++; } const dp = new Array(n1 + 1).fill(0); for (let i = 1; i <= n1; i++) { dp[i] = INF; } for (let i = 0; i < s.length; i++) { const c = s.charAt(i); for (let j = n1; j >= 1; j--) { if (c == '0' ) dp[j] = Math.min(dp[j], dp[j - 1] + n2 - j + 1); else dp[j] = Math.min(dp[j], dp[j - 1] + j - 1); } } return dp[n1]; } const S = "1010001" ; console.log(minimumCost(S)); // Output: 3 |
3
Time Complexity: O(N^2)
Auxiliary Space: O(N)
Contact Us