Minimum count of 0s to be selected such that all 1s are adjacent to them
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 buckets int 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 code int main() { string str = "1001" ; cout << minimumBuckets(str)<<endl; string str1 = "1010" ; cout << minimumBuckets(str1); return 0; } |
Java
// Java code to implement the above approach 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.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 buckets def 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 code if __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 approach using 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> |
2 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us