Given binary string str, consisting of only two characters ‘1‘ and ‘0‘, and an integer X, the task is to calculate the minimum cost to convert all the characters to ‘1’. The cost to convert one ‘0’ to ‘1’ is given as X and the cost to convert one ‘1’ to ‘0’ is X / 3. If a ‘0’ is converted to ‘1’ then all the 0s adjacently connected to it as a group to its left and right will be converted to ‘1’ without any cost.
Example:
Input: str = “101001”, X = 6
Output: 8
Explanation: Replace the character at index 2 i.e ‘1’ with ‘0’ which will take 6 / 3 =2 cost, then change it back to ‘1’ with the cost of 6 so that the string becomes “111111”Input: str = “10110100”, X = 3
Output: 6
Approach: The given problem can be solved using dynamic programming. Below steps can be followed to solve the problem:
- Declare an array dp[] to store the answers calculated
- Initialize the first element with INT_MAX
- If the first character of the string is ‘0‘ re-initialize the first element of dp[] with K.
- Traverse the string str and check for the following conditions:
- If the character is ‘1‘ and if dp[i-1] is not equal to INT_MAX, increment the sum by 1
- Else if character is ‘0‘:
- dp[i-1] is equal to INT_MAX, set dp[i] = k
- If the previous character was not equal to ‘0‘, calculate the minimum value and assign it to dp[i]
- Return dp[N] which is the desired answer
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum cost required// to replace all Bs with Asint replaceZerosWithOnes(string str, int K, int N){ // Declare an array to store // the temporary answer int dp[N + 1] = { 0 }; // Initialize the dp[0] with INT_MAX dp[0] = INT_MAX; int sum = 0; // If character is 'B' if (str[0] == '0') { // Re-initialize dp[0] to K dp[0] = K; } for (int i = 1; i < N; i++) { // If current character // is equal to A if (str[i] == '1') { // If dp[i-1] is not equal // to INT_MAX if (dp[i - 1] != INT_MAX) { // Increment sum by 1 sum++; } dp[i] = dp[i - 1]; } // If current character is 'B' // and dp[i-1] is equal to // INT_MAX else if (str[i] == '0' && dp[i - 1] == INT_MAX) { // Set dp[i] = k dp[i] = K; } // If current character is 'B' and // previous character was not 'B' else if (str[i] == '0' && str[i - 1] != '0') { // Calculate the minimum // value and assign it to dp[i] dp[i] = min((dp[i - 1] + (sum * K / 3)), dp[i - 1] + K); sum = 0; } // Else move next else dp[i] = dp[i - 1]; } // Return last element stored in dp return dp[N - 1];}// Driver Codeint main(){ string str = "10110100"; int N = str.size(); int K = 3; // Print the result of the function cout << replaceZerosWithOnes(str, K, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find minimum cost required// to replace all Bs with Asstatic int replaceZerosWithOnes(String str, int K, int N){ // Declare an array to store // the temporary answer int dp[] = new int[N + 1]; for (int i = 0; i < N + 1; i++) dp[i] = 0; // Initialize the dp[0] with INT_MAX dp[0] = Integer.MAX_VALUE; int sum = 0; // If character is 'B' if (str.charAt(0) == '0') { // Re-initialize dp[0] to K dp[0] = K; } for (int i = 1; i < N; i++) { // If current character // is equal to A if (str.charAt(i) == '1') { // If dp[i-1] is not equal // to INT_MAX if (dp[i - 1] != Integer.MAX_VALUE) { // Increment sum by 1 sum++; } dp[i] = dp[i - 1]; } // If current character is 'B' // and dp[i-1] is equal to // INT_MAX else if (str.charAt(i) == '0' && dp[i - 1] == Integer.MAX_VALUE) { // Set dp[i] = k dp[i] = K; } // If current character is 'B' and // previous character was not 'B' else if (str.charAt(i) == '0' && str.charAt(i - 1) != '0') { // Calculate the minimum // value and assign it to dp[i] dp[i] = Math.min((dp[i - 1] + (sum * K / 3)), dp[i - 1] + K); sum = 0; } // Else move next else dp[i] = dp[i - 1]; } // Return last element stored in dp return dp[N - 1];} // Driver codepublic static void main(String args[]){ String str = "10110100"; int N = str.length(); int K = 3; // Print the result of the function System.out.println(replaceZerosWithOnes(str, K, N)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# python implementation for the above approachINT_MAX = 2147483647# Function to find minimum cost required# to replace all Bs with Asdef replaceZerosWithOnes(str, K, N): # Declare an array to store # the temporary answer dp = [0 for _ in range(N + 1)] # Initialize the dp[0] with INT_MAX dp[0] = INT_MAX sum = 0 # If character is 'B' if (str[0] == '0'): # Re-initialize dp[0] to K dp[0] = K for i in range(1, N): # If current character # is equal to A if (str[i] == '1'): # If dp[i-1] is not equal # to INT_MAX if (dp[i - 1] != INT_MAX): # Increment sum by 1 sum += 1 dp[i] = dp[i - 1] # If current character is 'B' # and dp[i-1] is equal to # INT_MAX elif (str[i] == '0' and dp[i - 1] == INT_MAX): # Set dp[i] = k dp[i] = K # If current character is 'B' and # previous character was not 'B' elif (str[i] == '0' and str[i - 1] != '0'): # Calculate the minimum # value and assign it to dp[i] dp[i] = min((dp[i - 1] + ((sum * K) // 3)), dp[i - 1] + K) sum = 0 # Else move next else: dp[i] = dp[i - 1] # Return last element stored in dp return dp[N - 1]# Driver Codeif __name__ == "__main__": str = "10110100" N = len(str) K = 3 # Print the result of the function print(replaceZerosWithOnes(str, K, N))# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections;class GFG{// Function to find minimum cost required// to replace all Bs with Asstatic int replaceZerosWithOnes(string str, int K, int N){ // Declare an array to store // the temporary answer int []dp = new int[N + 1]; for (int i = 0; i < N + 1; i++) dp[i] = 0; // Initialize the dp[0] with INT_MAX dp[0] = Int32.MaxValue; int sum = 0; // If character is 'B' if (str[0] == '0') { // Re-initialize dp[0] to K dp[0] = K; } for (int i = 1; i < N; i++) { // If current character // is equal to A if (str[i] == '1') { // If dp[i-1] is not equal // to INT_MAX if (dp[i - 1] != Int32.MaxValue) { // Increment sum by 1 sum++; } dp[i] = dp[i - 1]; } // If current character is 'B' // and dp[i-1] is equal to // INT_MAX else if (str[i] == '0' && dp[i - 1] == Int32.MaxValue) { // Set dp[i] = k dp[i] = K; } // If current character is 'B' and // previous character was not 'B' else if (str[i] == '0' && str[i - 1] != '0') { // Calculate the minimum // value and assign it to dp[i] dp[i] = Math.Min((dp[i - 1] + (sum * K / 3)), dp[i - 1] + K); sum = 0; } // Else move next else dp[i] = dp[i - 1]; } // Return last element stored in dp return dp[N - 1];} // Driver codepublic static void Main(){ string str = "10110100"; int N = str.Length; int K = 3; // Print the result of the function Console.Write(replaceZerosWithOnes(str, K, N)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find minimum cost required // to replace all Bs with As function replaceZerosWithOnes(str, K, N) { // Declare an array to store // the temporary answer let dp = new Array(N + 1).fill(0) // Initialize the dp[0] with INT_MAX dp[0] = Number.MAX_VALUE; let sum = 0; // If character is 'B' if (str[0] == '0') { // Re-initialize dp[0] to K dp[0] = K; } for (let i = 1; i < N; i++) { // If current character // is equal to A if (str[i] == '1') { // If dp[i-1] is not equal // to INT_MAX if (dp[i - 1] != Number.MAX_VALUE) { // Increment sum by 1 sum++; } dp[i] = dp[i - 1]; } // If current character is 'B' // and dp[i-1] is equal to // INT_MAX else if (str[i] == '0' && dp[i - 1] == Number.MAX_VALUE) { // Set dp[i] = k dp[i] = K; } // If current character is 'B' and // previous character was not 'B' else if (str[i] == '0' && str[i - 1] != '0') { // Calculate the minimum // value and assign it to dp[i] dp[i] = Math.min((dp[i - 1] + (sum * K / 3)), dp[i - 1] + K); sum = 0; } // Else move next else dp[i] = dp[i - 1]; } // Return last element stored in dp return dp[N - 1]; } // Driver Code let str = "10110100"; let N = str.length; let K = 3; // Print the result of the function document.write(replaceZerosWithOnes(str, K, N)); // This code is contributed by Potta Lokesh </script> |
Output
6
Time Complexity: O(N)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
