Given a binary string str of size N whose every character is either ‘1’ or ‘0’. The task is to select minimum number of 0‘s such that at least one neighbor for every ‘1’ is selected. Print the count of the selected 0′s.
Examples:
Input: str = “1001”
Output: 2
Explanation: ‘0’s can be selected from index 1 and index 2. As a result, every ‘1’ has at least one neighbor present among the selected ‘0’s.Input: str = “01010”
Output: 1
Explanation: ‘0’ at index 2 can be selected. As a result one neighbor for both the ‘1’ s are selected.Input: str = “111”
Output: -1
Explanation: There is no ‘0’ in the given string. So there cannot be any neighbor of ‘1’ which is ‘0’.Input: str = “110”
Output: -1
Explanation: There is no ‘0’ as neighbor for ‘1’ at first position.
Approach: The solution is based on greedy approach. Follow the below steps to get the solution.
- Start iterating the string from the beginning.
- For each ‘1’ If possible, a ‘0’ is selected from its neighborhood.
- Now, if there is ‘0’ before as well as after current ‘1’, then always select the neighbor next to the current ‘1’ (because there can be more ‘1’s after this one and doing so will allow to select minimum number of neighbors).
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to count // minimum number of bucketsint minimumBuckets(string str){ int bucketcount = 0; int N = str.size(); // Loop to count minimum buckets for (int i = 0; i < N;) { if (str[i] == '1') { // If bucket can be put, // no need of next two indices, // so shift to i+3 if (i + 1 < N && str[i + 1] == '0') { bucketcount++; i += 3; continue; } if (i - 1 >= 0 && str[i - 1] == '0') { bucketcount++; i++; continue; } return -1; } i++; } return bucketcount;}// Driver codeint main(){ string str = "1001"; cout << minimumBuckets(str)<<endl; string str1 = "1010"; cout << minimumBuckets(str1); return 0;} |
Java
// Java code to implement the above approachclass GFG { // Function to count // minimum number of buckets static int minimumBuckets(String str) { int bucketcount = 0; int N = str.length(); // Loop to count minimum buckets for (int i = 0; i < N;) { if (str.charAt(i) == '1') { // If bucket can be put, // no need of next two indices, // so shift to i+3 if (i + 1 < N && str.charAt(i + 1) == '0') { bucketcount++; i += 3; continue; } if (i - 1 >= 0 && str.charAt(i - 1) == '0') { bucketcount++; i++; continue; } return -1; } i++; } return bucketcount; } // Driver code public static void main(String args[]) { String str = "1001"; System.out.println(minimumBuckets(str)); String str1 = "1010"; System.out.println(minimumBuckets(str1)); }}// This code is contributed by Saurabh Jaiswal |
Python3
# python code to implement the above approach# Function to count# minimum number of bucketsdef minimumBuckets(str): bucketcount = 0 N = len(str) # Loop to count minimum buckets i = 0 while(i < N): if (str[i] == '1'): # If bucket can be put, # no need of next two indices, # so shift to i+3 if (i + 1 < N and str[i + 1] == '0'): bucketcount += 1 i += 3 continue if (i - 1 >= 0 and str[i - 1] == '0'): bucketcount += 1 i += 1 continue return -1 i += 1 return bucketcount# Driver codeif __name__ == "__main__": str = "1001" print(minimumBuckets(str)) str1 = "1010" print(minimumBuckets(str1)) # This code is contributed by rakeshsahni |
C#
// C# code to implement the above approachusing System;class GFG { // Function to count // minimum number of buckets static int minimumBuckets(string str) { int bucketcount = 0; int N = str.Length; // Loop to count minimum buckets for (int i = 0; i < N;) { if (str[i] == '1') { // If bucket can be put, // no need of next two indices, // so shift to i+3 if (i + 1 < N && str[i + 1] == '0') { bucketcount++; i += 3; continue; } if (i - 1 >= 0 && str[i - 1] == '0') { bucketcount++; i++; continue; } return -1; } i++; } return bucketcount; } // Driver code public static void Main() { string str = "1001"; Console.WriteLine(minimumBuckets(str)); string str1 = "1010"; Console.WriteLine(minimumBuckets(str1)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to count // minimum number of buckets function minimumBuckets(str) { let bucketcount = 0; let N = str.length; // Loop to count minimum buckets for (let i = 0; i < N;) { if (str[i] == '1') { // If bucket can be put, // no need of next two indices, // so shift to i+3 if (i + 1 < N && str[i + 1] == '0') { bucketcount++; i += 3; continue; } if (i - 1 >= 0 && str[i - 1] == '0') { bucketcount++; i++; continue; } return -1; } i++; } return bucketcount; } // Driver code let str = "1001"; document.write(minimumBuckets(str) + '<br>'); let str1 = "1010"; document.write(minimumBuckets(str1) + '<br>'); // This code is contributed by Potta Lokesh </script> |
Output
2 1
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
