Approach
We can solve this problem using a straightforward approach. Let us try to minimize the number of zeros as much as possible. We can change all the zeros adjacent to 1s in the given binary string to any other character, say, *. We can then count the number of 1s and 0s left in the string and compare them.
Algorithm
- Take the input string 'STR.'
- Let 'N' be the size of the input string.
-
Run a for loop with variable i from 1 to 'N - 2' and check the following:
- If 'STR[i]' == '1' and 'STR[i-1]' == '0', 'STR[i-1]' = '*.'
- If 'STR[i]' == '1' and 'STR[i+1]' == '0', 'STR[i+1]' = '*.'
- Count the number of 1s and 0s in the modified binary string and output the answer.
Program
#include <iostream>
using namespace std;
bool compareCount(string &str)
{
// Size of the string.
int N = str.length();
// Run the for loop as described in the algorithm.
for (int i = 1; i < N - 1; i++)
{
if (str[i] == '1')
{
// Change the adjacent 0s.
if (str[i - 1] == '0')
str[i - 1] = '*';
if (str[i + 1] == '0')
str[i + 1] = '*';
}
}
// Count the 1s and 0s.
int count1 = 0, count0 = 0;
for (int i = 0; i < N; i++)
{
if (str[i] == '1')
count1++;
else if (str[i] == '0')
count0++;
}
// Compare the counts of 0s and 1s and return the appropriate answer.
if (count1 <= count0)
return false;
return true;
}
int main()
{
// Take the input.
string str;
cout << "Enter the string: ";
cin >> str;
// Find the output.
bool isPossible = compareCount(str);
// Print the answer.
if (isPossible)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
You can also try this code with Online C++ Compiler
Input
10010000001
Output
No
Time Complexity
The time complexity of the above approach is O(N), where 'N' is the size of the binary string. It is because we are running a single loop with 'N' as the limit to execute the algorithm.
Space Complexity
The space complexity of the above approach is O(1).
As we are using constant space to run the program.
Key Takeaways
In this blog, we discussed a problem based on greedy algorithms. Greedy algorithms are one of the most popular algorithms in technical interviews. It requires critical observations to identify the algorithm. Most of the time, it is easy to code a greedy algorithm, however, we may have to use set/map/multiset to implement a greedy approach in the proposed time limit.
Hence learning never stops, and there is a lot more to learn.
Check out this problem - Longest String Chain
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!
116+ registered 