Data Modelling & AI Data Structure & Algorithm

Minimize cost of swapping set bits with unset bits in a given Binary string

24 June 2025

0

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 i^th array element A[] with the j^th array element B[].
Now, for each state there are two choices:
1. Swap the i^th array element A[] till the (j – 1)^th array element B[] as dp[i][j] = dp[i][j – 1].
2. Swap the (i – 1)^th array element A[] till the (j – 1)^th array element B[] and the i^th array element A[] with j^th 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>

Output

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

Output

Time Complexity: O(N^2)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Minimize cost of swapping set bits with unset bits in a given Binary string

C++

Java

Python3

C#

Javascript

C++

Java

Python

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

One UI 8.5 might intelligently handle Wi-Fi and data swaps so you don’t have to

Samsung’s tri-folding phone flexes serious productivity skills in new leak

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

Waze just made hazard reporting as easy as talking

EDITOR PICKS

One UI 8.5 might intelligently handle Wi-Fi and data swaps so you don’t have to

Samsung’s tri-folding phone flexes serious productivity skills in new leak

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

POPULAR POSTS

One UI 8.5 might intelligently handle Wi-Fi and data swaps so you don’t have to

Samsung’s tri-folding phone flexes serious productivity skills in new leak

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

POPULAR CATEGORY

ABOUT US

FOLLOW US