Check if Count of 1s can be Made Greater in a Binary string by Changing 0s Adjacent to 1s

Aman kumar Chourasiya
Last Updated: May 13, 2022

Understanding

This blog addresses a coding challenge that involves the use of greedy algorithms. Greedy algorithms are one of the simplest-to-understand algorithms. The logic behind such algorithms can be speculated intuitively. In programming contests and technical interviews, problems based on greedy algorithms are increasingly asked to test your observation skills. 

Problem Statement

Ninja has given you a binary string. Your task is to determine if you can make the count of 1's in the binary string greater than that of 0's by changing the 0s adjacent to 1s to any other characters (except 1) any number of times.

If it is possible, output Yes, otherwise No.

Input

Enter the binary string: 1001

Output

Yes

Explanation

We can change all zeros in the given binary string to any other character. Then, the count of 1's will be 2, whereas the count of 0'w will be zero.

Modified binary string: 1*&1 (Other strings are also possible.)

Input

10010000001

Output

No

Explanation

It is not possible to make the count of 1's greater than that of 0's even if we replace all possible 0's adjacent to 1's.

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

  1. Take the input string 'STR.'
  2. Let 'N' be the size of the input string.
  3. Run a for loop with variable i from 1 to 'N - 2' and check the following:
    1. If 'STR[i]' == '1' and 'STR[i-1]' == '0', 'STR[i-1]' = '*.'
    2. If 'STR[i]' == '1' and 'STR[i+1]' == '0', 'STR[i+1]' = '*.'
  4. 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;
}

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.

So head over to our practice platform CodeStudio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!

Was this article helpful ?
0 upvotes