Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Understanding
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
2.4.
Input
2.5.
Output
2.6.
Explanation
3.
Approach
3.1.
Program
3.2.
Input
3.3.
Output
3.4.
Time Complexity
3.5.
Space Complexity
4.
Key Takeaways
Last Updated: Mar 27, 2024

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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. 

Recommended topic, kth largest element in an array, and Euclid GCD Algorithm

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.
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!

Previous article
Find the longest substring in a binary string with an equal count of 0s and 1s
Next article
Find the Length of Smallest Non-Prime Subsequence in a Numeric String
Live masterclass