Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example:
3.
Intuition
4.
Algorithm
5.
Implementation
5.1.
Example
6.
Complexity Analysis
7.
Key Takeaways
Last Updated: Mar 27, 2024

Minimize Cost to Convert all ‘0’s to ‘1’s with Cost of Converting ‘0’s Group be K and that of ‘1’ be K / 3

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

We all prepare data structures and algorithms to crack interviews of our dream companies. Questions related to binary strings are often asked during the interviews, and therefore, one is needed to ace on it with a lot of other topics to ensure their selection.

A binary string is a sequence of characters ‘0’ and ‘1’. Let us learn more about the binary strings from the below problem statement.

Problem Statement

The task is to calculate the minimum cost to convert all characters of a given binary string ‘S’ to ‘1’. The cost for conversion is explained as below:

  • The cost to convert a ‘0’ to ‘1’ is given as ‘K’, where if a ‘0’ is converted to ‘1’, then all the ‘0’s connected to it in left and right until another ‘1’ comes in the way, are also converted to ‘1’s without any cost
  • The cost to convert a ‘1’ to ‘0’ is given as ‘K / 3’

Example:

Input: S = “110001”, K = 9

Output: 9

Explanation: Converting ‘0’ to ‘1’ at index 2, at cost, K = 9, making the string S = “111111”

 

Input: S = “100010”, K = 3

Output: 4

Explanation: Cost can be calculated as:

  • Converting ‘1’ at index 4, to ‘0’ at cost K / 3 = 1, making string as S = “100000”
  • Converting ‘0’ at index 1, at cost K = 3, making string as S = “111111”
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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!

 

Previous article
Find the Minimum Insertions in the Given String to Form a Palindrome
Next article
Decode ways
Live masterclass