Given a binary sequence of 1‘s and 0‘s. Our task is to remove all 1s from the sequence in minimum cost by below operations.
- Remove an element from the left end (i.e., remove s[0]) which costs 1 coin.
- Remove an element from the right end (i.e., remove s[s.length – 1]) which costs 1 coin.
- Remove an element from anywhere in the sequence which costs 2 coins.
Return the minimum cost to remove all the 1s from the sequence.
Examples:
Input: s = “1100101”
Output: 5
Explanation:
Remove left most “1100101″ in cost of 1 coin, new s = “100101”
Remove left most “100101″ in cost of 1 coin, new s = “00101”
Remove right most “00101” in cost of 1 coin, new s = “0010”
Remove middle 1 (“0010″) in cost of 2 coin, new s = “000”.
So total 5 coins are requiredInput: s = “0010”
Output: 2
Explanation: Remove middle 1 (“0010”) in cost of 2 coin, new s = “000”
Approach: The idea is to use DP with sliding window. Use an array dp[N] where dp[i] stores the minimum coin to remove all 1s from index i to n-1, where we can only remove from right. Follow the below steps.
- Loop from the rightmost index. So, for any index i the transition is as follows:
- If it’s a ‘0’ then dp[i]=dp[i+1]
- If it’s a ‘1’ then we have two options – either consider this element as a middle one and add 2 to dp[i+1] or remove all elements. Hence, dp[i]=min(dp[i+1]+2, n-i)
- Now, also remove elements from left. So, loop over the vector.
- When we reach any index i, we will consider that we have removed all elements from 0 to i from the leftside.
- So, our time for that index will be i+1+dp[i+1].
- Since, we have removed all elements until i, we need to just consider elements from i+1 and hence we are adding the dp[i+1] to our i+1.
- Finally return minimum answer
Below is the code implementation:
C++
// C++ program for find the minimum cost// to remove all 1's from the given binary string#include <bits/stdc++.h>using namespace std;// Function to find minimum costint minimumCoin(string s){ int n = s.length(); vector<int> dp(n, 0); if (s[n - 1] == '0') { dp[n - 1] = 0; } else { dp[n - 1] = 1; } for (int i = n - 2; i >= 0; i--) { if (s[i] == '0') dp[i] = dp[i + 1]; if (s[i] == '1') { // consider current index to // be a middle one and remove dp[i] = 2 + dp[i + 1]; // or remove all to the right dp[i] = min(dp[i], n - i); } } // now go from left to right int ans = dp[0]; for (int i = 0; i < n - 1; i++) { // cost of removing all // from left and dp[i+1] ans = min(ans, i + 1 + dp[i + 1]); } // taking overall minimum ans = min(ans, n); return ans;}// Driver functionint main(){ string str = "1001001"; int coins = minimumCoin(str); cout << coins; return 0;} |
Java
//Java program for find the minimum cost// to remove all 1's from the given binary stringimport java.io.*;class GFG { // Function to find minimum cost static int minimumCoin(String s) { int n = s.length(); int dp[] = new int[n]; if (s.charAt(n - 1) == '0') { dp[n - 1] = 0; } else { dp[n - 1] = 1; } for (int i = n - 2; i >= 0; i--) { if (s.charAt(i) == '0') dp[i] = dp[i + 1]; if (s.charAt(i) == '1') { // consider current index to // be a middle one and remove dp[i] = 2 + dp[i + 1]; // or remove all to the right dp[i] = Math.min(dp[i], n - i); } } // now go from left to right int ans = dp[0]; for (int i = 0; i < n - 1; i++) { // cost of removing all // from left and dp[i+1] ans = Math.min(ans, i + 1 + dp[i + 1]); } // taking overall minimum ans = Math.min(ans, n); return ans; } // Driver function public static void main (String[] args) { String str = "1001001"; int coins = minimumCoin(str); System.out.println(coins); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python code for the above approach# Function to find minimum costdef minimumCoin(s): n = len(s) dp = [0]*n if (s[n - 1] == '0'): dp[n - 1] = 0 else: dp[n - 1] = 1 for i in range(n-2, -1, -1): if s[i] == '0': dp[i] = dp[i + 1] if s[i] == '1': # consider current index to # be a middle one and remove dp[i] = 2 + dp[i + 1] # or remove all to the right dp[i] = min(dp[i], n - i) # now go from left to right ans = dp[0] for i in range(0, n-1): # cost of removing all # from left and dp[i+1] ans = min(ans, i + 1 + dp[i + 1]) # taking overall minimum ans = min(ans, n) return ans# Driver functionstr = "1001001"coins = minimumCoin(str)print(coins)# This code is contributed by Potta Lokesh |
C#
// C# program for find the minimum cost// to remove all 1's from the given binary stringusing System;class GFG { // Function to find minimum cost static int minimumCoin(string s) { int n = s.Length; int[] dp = new int[n]; if (s[n - 1] == '0') { dp[n - 1] = 0; } else { dp[n - 1] = 1; } for (int i = n - 2; i >= 0; i--) { if (s[i] == '0') dp[i] = dp[i + 1]; if (s[i] == '1') { // consider current index to // be a middle one and remove dp[i] = 2 + dp[i + 1]; // or remove all to the right dp[i] = Math.Min(dp[i], n - i); } } // now go from left to right int ans = dp[0]; for (int i = 0; i < n - 1; i++) { // cost of removing all // from left and dp[i+1] ans = Math.Min(ans, i + 1 + dp[i + 1]); } // taking overall minimum ans = Math.Min(ans, n); return ans; } // Driver function public static void Main() { string str = "1001001"; int coins = minimumCoin(str); Console.Write(coins); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for find the minimum cost // to remove all 1's from the given binary string // Function to find minimum cost const minimumCoin = (s) => { let n = s.length; let dp = new Array(n).fill(0); if (s[n - 1] == '0') { dp[n - 1] = 0; } else { dp[n - 1] = 1; } for (let i = n - 2; i >= 0; i--) { if (s[i] == '0') dp[i] = dp[i + 1]; if (s[i] == '1') { // consider current index to // be a middle one and remove dp[i] = 2 + dp[i + 1]; // or remove all to the right dp[i] = Math.min(dp[i], n - i); } } // now go from left to right let ans = dp[0]; for (let i = 0; i < n - 1; i++) { // cost of removing all // from left and dp[i+1] ans = Math.min(ans, i + 1 + dp[i + 1]); } // taking overall minimum ans = Math.min(ans, n); return ans; } // Driver function let str = "1001001"; let coins = minimumCoin(str); document.write(coins);// This code is contributed by rakeshsahni</script> |
Output
4
Time complexity: O(n)
Space complexity: 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!