Minimize cost to convert all characters of a binary string to 0s

Riya
Last Updated: May 13, 2022

Introduction-  

This article will discuss the problem "Minimize cost to convert all characters of a binary string to 0s", in which we have to find the minimum cost to convert all characters of a binary string to 0s. Before understanding the problem, first, recall what a binary string is.

A binary string is a string that contains either '0' or '1'.

We get a binary string 'S' and two arrays containing integers in this problem. The two integer arrays are "right[]" and "cost[]". It is given that there will be a cost of 'cost[i]' to flip all the characters of 'S' from index 'i' to 'right[i]'. And, we have to find the minimum cost to convert all characters of the given binary string to 0s.

 

Let’s take an example to understand the question:

Assume given   S = “10010” ,

                       right[5] = {1, 3, 3, 4, 4} and

                       cost[5] = {3, 4, 6, 2, 1}

We have to find the minimum cost to convert the given binary string 'S' to "00000". We can flip characters in the string from index 'i' to index' right[i]' with a cost of cost[i].

Now, we have understood the question. Let's discuss the approach to find the minimum cost to convert all characters of a binary string to 0s in the next section.

 

Solution Approach

We will be using a greedy approach to find the minimum cost to convert all characters of a binary string to 0s. The approach is to traverse the string from left to right, and if the current character is not '0', we need to convert all the characters from the current index 'i' to 'right[i]'. After flipping the characters, we will store the index up to which we have flipped the characters to keep track of the flipped characters, and along with it, we will keep track of the total number of flips of the current character. Also, we will declare a variable for storing the minimum cost, and whenever we flip characters, we will add its cost to the minimum cost variable. In this way, after traversing the whole string, we will find the minimum cost to convert all the characters of a binary string to 0s.

                                                                               

Algorithm -

Step 1. Create a function "minimizeCost()" .to find the minimum cost to convert all characters of a binary string to 0s. It will take the following input:

  1. S - Given binary string
  2. N - Length of given binary string
  3. right[] - Given array of right indices 
  4. cost[] - Given array of cost

Step 2. Initialize two variables ‘current_flips = 0’ and  ‘min_cost = 0’ to store the number of flips of current character and minimum cost to convert all characters of a binary string to 0s respectively. 

Step 3 Create a priority queue to store the indices up to which number of flips is greater than zero and which will store the lowest element at the top.

Step 4. Now traverse the string from left to right and if the number of flips for the current character is odd, then update it. Then check if it is not equal to ‘0’, flip it, increase the value of ‘current_flip’ and ‘min_cost’, and insert the value of right[i] into the priority queue.

Step 5. Finally, after traversing the string, return the calculated value of minimum cost to convert all the characters of a binary string to 0s.

 

C++ code:

// C++ code to find the minimum cost to convert all characters of a binary string to 0s 
#include <bits/stdc++.h>
using namespace std;


//Function to find minimum cost to convert all characters of a binary string to 0s
int minimizeCost(string s, int n, int right[], int cost[])
{


/*
            Priority queue to store the right indices 
            upto which characters are flipped
       */
priority_queue<int, vector<int>, greater<int> > pq;
 
// Variable to store the minimum cost
int min_cost = 0;
 
// Variable to store the number of flips of current character
int current_flip = 0;
 
// Traverse the string from left to right
for (int i = 0; i < n; i++)
       {


          // Remove the indices which are left of the current index
          while (pq.size() > 0 and pq.top() < i)
          {
             pq.pop();
            
             /*
                 Decrease the value of current flip as we are 
                 removing one flip from the priority queue
             */
             current_flip--;
          }
        
        // Check if current_flip is odd, then flip the current character
        if (current_flip % 2 == 1)
        {
            if(s[i]=='1') {
             s[i]='0';
            }
            else s[i]='1';
        }
        
        // Now, check if current character is '1', then flip it 
        if (s[i] == '1')
        {
         // Increase the count of current_flip
            current_flip++;
            
            // Increase the min_cost by cost[i]
            min_cost += cost[i];
            
            /*
                As we have now flipped till right[i], 
                add the right[i] index in priority queue
            */
            pq.push(right[i]);
        }
     }
     
    // Return the calculated minimum cost
    return min_cost;
}


int main()
{
    string s = "10010";
    int right[] = {1, 3, 3, 4, 4};
    int cost[] = {3, 4, 6, 2, 1};
    
    // Find the length of the given string
    int n = s.length();
   
    /*
        Call the function to find minimum cost to 
        convert all characters of a binary string to 0s
    */
    int minimumCost = minimizeCost(s, n, right, cost);
    
    cout<<"The minimum cost to convert all characters of given binary string to 0s is "<<minimumCost<<endl;
}

 

Output:
The minimum cost to convert all characters of given binary string to 0s is 16

 

Algorithm Complexity: 

Time Complexity: O(Nlog(N))

In the function "minimizeCost()" to find the minimum cost to convert all characters of a binary string to 0s, we have created a priority queue and inserted elements of the given binary string to it and the time complexity of inserting an element to priority queue is O(N). So, time complexity will be O(Nlog(N)), where ‘N’ is the length of the given binary string.

Space Complexity: O(N) 

In the function "minimizeCost()" to find the minimum cost to convert all characters of a binary string to 0s, we have created a priority queue and inserted elements of the given binary string. So, the space complexity will be O(N)

 

Frequently asked questions-

  1. What is the time complexity of inserting an element into a priority queue?

The time complexity of inserting an element into a priority queue is O(logN), where ‘N’ is the number of elements in it.


2. Why we have used a priority queue which is storing the minimum value at its top?

As we are traversing the string from left to right and fixing the elements from left to right. We need to get first the minimum index which is flipped so that first we can process it and then move ahead. So, we need to store the indices in the priority queue in such a way that the minimum index will be at the top.

 

Key takeaways-

This article discussed the problem of finding the minimum cost to convert all characters of a binary string to 0s, the approach to solve it, its C++ implementation, and its time and space complexities. If you want to practice problems of data structures and algorithms then you can visit codestudio.

 

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

 

Until then, All the best for your future endeavors, and Keep Coding.

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think