Intuition
The cost has to be minimized, so we need to check every possible way to convert the array such that it only contains ‘1’s. Thus, this problem can be solved with a Dynamic Programming Approach.
One more thought which needs to be observed here is whenever we will be converting a ‘1’ to ‘0’, it will be done to meet the two groups of ‘0’s on its left and right so that the whole new group can be converted to ‘1’s with a single conversion. Therefore, when we convert a ‘1’ to ‘0’, we need to convert all the ‘1’s of its group.
The solution can be understood from the below algorithm.
Algorithm
- The function findMinCost() will be used to find out the minimum cost for conversion.
-
In function findMinCost(), vector DP of size N, where N is the size of the string, will be used to store the minimum cost.
- For some index ‘i’, dp[i] will be storing the minimum cost for conversion of the string from index 0 to index i.
-
The vector dp will be initialized with ‘0’ at all indices. 0th index of vector dp stores
- K, if the 0th index of string S stores ‘0.’
- INT_MAX, if the 0th index of string S stores ‘1.’
- Declare a variable ‘count’, and initialize it to zero to count the number of ‘1’s in any group.
-
Iterating through the string, if the current index stores ‘1’, then we will perform
dp[i] = dp[i - 1]
- If there is a ‘0’ before the current index, then we will increment the variable ‘count’.
-
Else if the current index stores ‘0’, then we will check
-
If this is the first ‘0’ of the string s, then we can simply perform
dp[i] = K
-
Else we will perform
dp[i] = min(dp[i - 1] + count * (K / 3), dp[i - 1] + K)
i.e., we will check the conversion of the group of ‘1’s between this group, and the previous group of ‘0’s will generate less cost for us, or the conversion of this new group of ‘0’s to ‘1’s will be a good choice
- Finally, return dp[N - 1], the cost to convert the string from index 0 to index N - 1, where ‘N’ is the size of the string s
Below is the implementation of the above algorithm.
Implementation
// Program to find minimum cost for the conversion of binary string.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Function to find the minimum cost with Dynamic Programming.
int findMinCost(string s, int K)
{
// Storing the size of the string, s.
int N = s.length();
// Vector to store minimum costs.
vector<int> dp(N + 1, 0);
// Initializing the first element.
if (s[0] == '0')
dp[0] = K;
else
dp[0] = INT_MAX;
// Variable to store the count of '1's in a group.
int count = 0;
// Iterating through the string and finding the minimum cost.
for (int i = 1; i < N; i++)
{
if (s[i] == '0' && dp[i - 1] == INT_MAX)
dp[i] = K;
else if (s[i] == '0')
{
dp[i] = min(dp[i - 1] + count * (K / 3), dp[i - 1] + K);
count = 0;
}
else
{
dp[i] = dp[i - 1];
if (dp[i - 1] != INT_MAX)
count++;
}
}
// If no '0' is present in the string s.
if (dp[N - 1] == INT_MAX)
dp[N - 1] = 0;
// Returning the final result.
return dp[N - 1];
}
// Main function.
int main()
{
// Input of string s and K.
string s;
int K;
cin >> s >> K;
// Output for the final result.
cout << "Minimum cost for the conversion: " << findMinCost(s, K);
return 0;
}
You can also try this code with Online C++ Compiler
Example
Input
s = “101000111”
K = 6
Output
Minimum cost for the conversion: 8
Complexity Analysis
Time Complexity:
O(N), where ‘N’ is the size of string ‘S’.
Explanation: Iterating the string from 1 to ‘N’, sums up to O(N)
Space Complexity:
O(N), where ‘N’ is the size of string ‘S’.
Explanation: The vector ‘dp’ used to store the costs is having the size ‘N’, occupying the space O(N)
Key Takeaways
The above blog has covered an important interview question frequently asked in big MNCs where Data Structures and Algorithms play an important role. ‘Minimize cost to convert all ‘0’s to ‘1’s with the cost of converting ‘0’s group be K and that of ‘1’ be K / 3’ is a good question related to binary strings, which also enhances your understanding of Dynamic Programming.
Check out this problem - Frog Jump
Find more such interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.
Happy Coding!
34+ registered 
