Minimize cost to convert all characters of a binary string to 0s
Given a binary string, str, two integer arrays R[], and C[] of size N. Flipping all the characters from index i to R[i] requires C[i] cost. The task is to minimize the cost required to convert the given binary string to only 0s.
Examples:
Input: str = “1010”, R[] = {1, 2, 2, 3}, C[] = {3, 1, 2, 3}
Output: 4
Explanation:
Flipping all the characters from index 1 to 2, modifies str to “1100”. Therefore, cost = 1
Flipping all the characters from index 1 to 2, modifies str to “0000”. Therefore, cost = cost + 3 = 4
Therefore, minimum cost required is 4.Input: str = “01100”, R[] = {1, 2, 3, 4, 5}, C[] = {1, 5, 5, 2, 3}
Output: 10
Approach: The problem can be solved using Greedy technique. The idea is to traverse the given string from left to right and check if the current character is a non-zero character or not. If found to be true, then flip all the characters from the current index (= i) to R[i]th index. Follow the steps below to solve the problem:
- Initialize a variable, say flip, to store the number of times current character can be flipped.
- Create a priority queue, say pq to store the range of indexes of characters on the right side of current character whose flip value is greater than 0.
- Initialize a variable, say cost to store the minimum cost to obtain the required string.
- Traverse the given string and check if the current character is ‘1‘ or not. If found to be true, then flip all the characters in the range i to R[i] and increment the value of cost by C[i].
- Finally, print the value of cost.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to get the minimum // Cost to convert all characters // of given string to 0s int minCost(string str, int N, int R[], int C[]) { // Stores the range of indexes // of characters that need // to be flipped priority_queue< int , vector< int >, greater< int > > pq; // Stores the number of times // current character is flipped int flip = 0; // Stores minimum cost to get // the required string int cost = 0; // Traverse the given string for ( int i = 0; i < N; i++) { // Remove all value from pq // whose value is less than i while (pq.size() > 0 and pq.top() < i) { pq.pop(); // Update flip flip--; } // If current character // is flipped odd times if (flip % 2 == 1) { str[i] = '1' - str[i] + '0' ; } // If current character contains // non-zero value if (str[i] == '1' ) { // Update flip flip++; // Update cost cost += C[i]; // Append R[i] into pq pq.push(R[i]); } } return cost; } // Driver Code int main() { string str = "1010" ; int R[] = { 1, 2, 2, 3 }; int C[] = { 3, 1, 2, 3 }; int N = str.length(); // Function call cout << minCost(str, N, R, C); } |
Java
// Java program to implement // the above approach import java.util.*; import java.lang.*; import java.io.*; class GFG { // Function to get the minimum // Cost to convert all characters // of given string to 0s public static int minCost(String s, int R[], int C[], int N) { char ch[] = s.toCharArray(); // Stores the range of indexes // of characters that need // to be flipped PriorityQueue<Integer> pq = new PriorityQueue<>(); // Stores the number of times // current character is flipped int flip = 0 ; // Stores minimum cost to get // the required string int cost = 0 ; // Traverse the given string for ( int i = 0 ; i < N; i++) { // Remove all value from pq // whose value is less than i while (pq.size() > 0 && pq.peek() < i) { pq.poll(); // Update flip flip--; } // Get the current number int cn = ch[i] - '0' ; // If current character // is flipped odd times if (flip % 2 == 1 ) cn = 1 - cn; // If current character contains // non-zero value if (cn == 1 ) { // Update flip flip++; // Update cost cost += C[i]; // Append R[i] into pq pq.add(R[i]); } } return cost; } // Driver Code public static void main(String[] args) { int N = 4 ; String s = "1010" ; int R[] = { 1 , 2 , 2 , 3 }; int C[] = { 3 , 1 , 2 , 3 }; // Function call System.out.println(minCost(s, R, C, N)); } } |
Python3
# Python3 program to implement # the above approach # Function to get the minimum # Cost to convert all characters # of given string to 0s def minCost(s, R, C, N) : ch = list (s) # Stores the range of indexes # of characters that need # to be flipped pq = [] # Stores the number of times # current character is flipped flip = 0 # Stores minimum cost to get # the required string cost = 0 # Traverse the given string for i in range (N) : # Remove all value from pq # whose value is less than i while ( len (pq) > 0 and pq[ 0 ] < i) : pq.pop( 0 ); # Update flip flip - = 1 # Get the current number cn = ord (ch[i]) - ord ( '0' ) # If current character # is flipped odd times if (flip % 2 = = 1 ) : cn = 1 - cn # If current character contains # non-zero value if (cn = = 1 ) : # Update flip flip + = 1 # Update cost cost + = C[i] # Append R[i] into pq pq.append(R[i]) return cost # Driver code N = 4 s = "1010" R = [ 1 , 2 , 2 , 3 ] C = [ 3 , 1 , 2 , 3 ] # Function call print (minCost(s, R, C, N)) # This code is contributed by divyeshrabadiya07. |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to get the minimum // Cost to convert all characters // of given string to 0s public static int minCost(String s, int []R, int []C, int N) { char []ch = s.ToCharArray(); // Stores the range of indexes // of characters that need // to be flipped Queue< int > pq = new Queue< int >(); // Stores the number of times // current character is flipped int flip = 0; // Stores minimum cost to get // the required string int cost = 0; // Traverse the given string for ( int i = 0; i < N; i++) { // Remove all value from pq // whose value is less than i while (pq.Count > 0 && pq.Peek() < i) { pq.Dequeue(); // Update flip flip--; } // Get the current number int cn = ch[i] - '0' ; // If current character // is flipped odd times if (flip % 2 == 1) cn = 1 - cn; // If current character contains // non-zero value if (cn == 1) { // Update flip flip++; // Update cost cost += C[i]; // Append R[i] into pq pq.Enqueue(R[i]); } } return cost; } // Driver Code public static void Main(String[] args) { int N = 4; String s = "1010" ; int []R = { 1, 2, 2, 3 }; int []C = { 3, 1, 2, 3 }; // Function call Console.WriteLine(minCost(s, R, C, N)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program to implement // the above approach // Function to get the minimum // Cost to convert all characters // of given string to 0s function minCost(str, N, R, C) { str = str.split( '' ); // Stores the range of indexes // of characters that need // to be flipped var pq = []; // Stores the number of times // current character is flipped var flip = 0; // Stores minimum cost to get // the required string var cost = 0; // Traverse the given string for ( var i = 0; i < N; i++) { // Remove all value from pq // whose value is less than i while (pq.length > 0 && pq[pq.length-1] < i) { pq.pop(); // Update flip flip--; } // If current character // is flipped odd times if (flip % 2 == 1) { str[i] = String.fromCharCode( '1' .charCodeAt(0) - str[i].charCodeAt(0) + '0' .charCodeAt(0)); } // If current character contains // non-zero value if (str[i] == '1' ) { // Update flip flip++; // Update cost cost += C[i]; // Append R[i] into pq pq.push(R[i]); } pq.sort((a,b)=>b-a); } return cost; } // Driver Code var str = "1010" ; var R = [1, 2, 2, 3 ]; var C = [3, 1, 2, 3 ]; var N = str.length; // Function call document.write(minCost(str, N, R, C)); // This code is contributed by noob2000. </script> |
4
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Contact Us