# 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**.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Examples:**

Input:S = “1010001”Output:3Explanation:

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 that**dp[i][j]**stores the minimum cost of swapping the**i**array element^{th}**A[]**with the**j**array element^{th}**B[]**. - Now, for each state there are two choices:
- Swap the
**i**array element^{th}**A[]**till the**(j – 1)**array element^{th}**B[]**as**dp[i][j] = dp[i][j – 1]**. - Swap the
**(i – 1)**array element^{th}**A[]**till the**(j – 1)**array element^{th}**B[]**and the**i**array element^{th}**A[]**with**j**array element^{th}**B[]**and this state can be calculated as**dp[i][j] = dp[i – 1][j – 1] + abs(A[i] – B[i])**.

- Swap the
- 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;` `}` |

## 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>` |

**Output:**

3

**Time Complexity:** O(K*(N – K)) where K is the *count of set bit** in S.*

**Auxiliary Space:**O(K*(N – K))