# Check if count of 1s can be made greater in a Binary string by changing 0s adjacent to 1s

Given a binary string **S** of size **N**, the task is to check if the count of **1s** can be made greater than the count of **0s** by changing the **0s** adjacent to **1s** to any other characters. If it is possible, then print **Yes**. Otherwise, print **No**.

**Note:** Any index having **1 **can be chosen at most once.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Examples:**

Input:S = “01”Output:YesExplanation:

Choose ‘1’ at index 1 and change its left adjacent 0 to ‘_’, modifies the string to “_1”.

Now, the count of 1s is 1 which is greater than the count of 0’s i.e., 0. Therefore, print Yes.

Input:S = “001110000”Output:No

**Approach:** The given problem can be solved by counting the number of **1s** and **0s** in the string **S** and then while traversing the string if any index **i** at which the value is **‘1’** and if left-side or right-side(Not Both) is **‘0’** then change it to **‘_’**. The value is changed to **‘_’** and not **‘1’** so that it is not used again. After changing the value, decrease the count of **0’s** by **1**. Follow the steps below to solve the problem:

- Initialize two variables, say
**cnt0**and**cnt1**as**0**to store the count of**0s**and**1s**. - Traverse the string
**S**and store the count of**1s**and**0s**in the variables**cnt0**and**cnt1**respectively. - Traverse the string
**S**from the left side and check current character is**1**if found to be true then check for the condition:**if(i > 0 && S[i – 1] == ‘0’)**if it is found to be true then change the left adjacent 0 to**S[i-1] = ‘_’**and decrement the value of**cnt0**by**1**.**else if(i < S.length() && S[i+1] == ‘0’)**if it is found to be true then change the right 0 to**S[i+1] = ‘_’**and decrement the value of**cnt0**by**1**.

- After completing the above steps, if the value of
**(cnt1 > cnt0)**, then print**“Yes”**. Otherwise, print**“No”**.

Below is the implementation for the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to check whether in a given` `// binary string can we make number of` `// 1's greater than the number of 0's` `// by doing the given operation` `void` `isOnesGreater(string S, ` `int` `N)` `{` ` ` `// Stores the count of 0's` ` ` `int` `cnt0 = 0;` ` ` `// Stores the count of 1's` ` ` `int` `cnt1 = 0;` ` ` `// Traverse through the string S` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Check current character is 1` ` ` `if` `(S[i] == ` `'1'` `)` ` ` `// Update cnt1` ` ` `cnt1++;` ` ` `else` ` ` `// Update cnt0` ` ` `cnt0++;` ` ` `}` ` ` `// Traverse through the string S` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Check curretn character is 1` ` ` `if` `(S[i] == ` `'1'` `) {` ` ` `// Check if left adjacent` ` ` `// character is 0` ` ` `if` `(i > 0 && S[i - 1] == ` `'0'` `) {` ` ` `// Change the left adjacent` ` ` `// character to _` ` ` `S[i - 1] = ` `'_'` `;` ` ` `// Update the cnt0` ` ` `cnt0--;` ` ` `}` ` ` `// Check if right adjacent` ` ` `// character is 0` ` ` `else` `if` `(i < N && S[i + 1] == ` `'0'` `) {` ` ` `// Change the right adjacent` ` ` `// character to _` ` ` `S[i + 1] = ` `'_'` `;` ` ` `// Update the cnt0` ` ` `cnt0--;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Check count of 1's is greater` ` ` `// than the count of 0's` ` ` `if` `(cnt1 > cnt0) {` ` ` `cout << ` `"Yes"` `;` ` ` `}` ` ` `else` `{` ` ` `cout << ` `"No"` `;` ` ` `}` `}` `// Driver Code` `int` `main()` `{` ` ` `string S = ` `"01"` `;` ` ` `int` `N = S.length();` ` ` `isOnesGreater(S, N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG {` ` ` `// Function to check whether in a given` ` ` `// binary string can we make number of` ` ` `// 1's greater than the number of 0's` ` ` `// by doing the given operation` ` ` `static` `void` `isOnesGreater(String S, ` `int` `N)` ` ` `{` ` ` `char` `[] st = ` `new` `char` `[S.length()];` ` ` ` ` `// Copy character by character into array` ` ` `for` `(` `int` `i = ` `0` `; i < S.length(); i++) {` ` ` `st[i] = S.charAt(i);` ` ` `}` ` ` ` ` `// Stores the count of 0's` ` ` `int` `cnt0 = ` `0` `;` ` ` `// Stores the count of 1's` ` ` `int` `cnt1 = ` `0` `;` ` ` `// Traverse through the string S` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `// Check current character is 1` ` ` `if` `(st[i] == ` `'1'` `)` ` ` `// Update cnt1` ` ` `cnt1++;` ` ` `else` ` ` `// Update cnt0` ` ` `cnt0++;` ` ` `}` ` ` `// Traverse through the string S` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `// Check curretn character is 1` ` ` `if` `(st[i] == ` `'1'` `) {` ` ` `// Check if left adjacent` ` ` `// character is 0` ` ` `if` `(i > ` `0` `&& st[i - ` `1` `] == ` `'0'` `) {` ` ` `// Change the left adjacent` ` ` `// character to _` ` ` `st[i - ` `1` `] = ` `'_'` `;` ` ` `// Update the cnt0` ` ` `cnt0--;` ` ` `}` ` ` `// Check if right adjacent` ` ` `// character is 0` ` ` `else` `if` `(i < N && st[i + ` `1` `] == ` `'0'` `) {` ` ` `// Change the right adjacent` ` ` `// character to _` ` ` `st[i + ` `1` `] = ` `'_'` `;` ` ` `// Update the cnt0` ` ` `cnt0--;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Check count of 1's is greater` ` ` `// than the count of 0's` ` ` `if` `(cnt1 > cnt0) {` ` ` `System.out.println(` `"Yes"` `);` ` ` `}` ` ` `else` `{` ` ` `System.out.println(` `"No"` `);` ` ` `}` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String args[])` ` ` `{` ` ` `String S = ` `"01"` `;` ` ` `int` `N = S.length();` ` ` `isOnesGreater(S, N);` ` ` `}` `}` `// This code is contributed by bgangwar59.` |

## Python3

`# Python Program to implement` `# the above approach` `# Function to check whether in a given` `# binary string can we make number of` `# 1's greater than the number of 0's` `# by doing the given operation` `def` `isOnesGreater(S, N):` ` ` `S ` `=` `list` `(S)` ` ` ` ` `# Stores the count of 0's` ` ` `cnt0 ` `=` `0` ` ` `# Stores the count of 1's` ` ` `cnt1 ` `=` `0` ` ` `# Traverse through the string S` ` ` `for` `i ` `in` `range` `(N):` ` ` `# Check current character is 1` ` ` `if` `(S[i] ` `=` `=` `'1'` `):` ` ` `# Update cnt1` ` ` `cnt1 ` `+` `=` `1` ` ` `else` `:` ` ` `# Update cnt0` ` ` `cnt0 ` `+` `=` `1` ` ` ` ` `# Traverse through the string S` ` ` `for` `i ` `in` `range` `(N):` ` ` `# Check curretn character is 1` ` ` `if` `(S[i] ` `=` `=` `'1'` `):` ` ` `# Check if left adjacent` ` ` `# character is 0` ` ` `if` `(i > ` `0` `and` `S[i ` `-` `1` `] ` `=` `=` `'0'` `):` ` ` `# Change the left adjacent` ` ` `# character to _` ` ` `S[i ` `-` `1` `] ` `=` `'_'` ` ` `# Update the cnt0` ` ` `cnt0 ` `-` `=` `1` ` ` ` ` `# Check if right adjacent` ` ` `# character is 0` ` ` `elif` `(i < N ` `and` `S[i ` `+` `1` `] ` `=` `=` `'0'` `):` ` ` `# Change the right adjacent` ` ` `# character to _` ` ` `S[i ` `+` `1` `] ` `=` `'_'` ` ` `# Update the cnt0` ` ` `cnt0 ` `-` `=` `1` ` ` `# Check count of 1's is greater` ` ` `# than the count of 0's` ` ` `if` `(cnt1 > cnt0):` ` ` `print` `(` `"Yes"` `)` ` ` `else` `:` ` ` `print` `(` `"No"` `)` `# Driver Code` `S ` `=` `"01"` `N ` `=` `len` `(S)` `isOnesGreater(S, N)` `# This code is contributed by gfgking` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Text;` `class` `GFG {` ` ` `// Function to check whether in a given` ` ` `// binary string can we make number of` ` ` `// 1's greater than the number of 0's` ` ` `// by doing the given operation` ` ` `static` `void` `isOnesGreater(` `string` `S, ` `int` `N)` ` ` `{` ` ` `StringBuilder st = ` `new` `StringBuilder(S);` ` ` `// Stores the count of 0's` ` ` `int` `cnt0 = 0;` ` ` `// Stores the count of 1's` ` ` `int` `cnt1 = 0;` ` ` `// Traverse through the string S` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Check current character is 1` ` ` `if` `(st[i] == ` `'1'` `)` ` ` `// Update cnt1` ` ` `cnt1++;` ` ` `else` ` ` `// Update cnt0` ` ` `cnt0++;` ` ` `}` ` ` `// Traverse through the string S` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// Check curretn character is 1` ` ` `if` `(st[i] == ` `'1'` `) {` ` ` `// Check if left adjacent` ` ` `// character is 0` ` ` `if` `(i > 0 && st[i - 1] == ` `'0'` `) {` ` ` `// Change the left adjacent` ` ` `// character to _` ` ` `st[i - 1] = ` `'_'` `;` ` ` `// Update the cnt0` ` ` `cnt0--;` ` ` `}` ` ` `// Check if right adjacent` ` ` `// character is 0` ` ` `else` `if` `(i < N && st[i + 1] == ` `'0'` `) {` ` ` `// Change the right adjacent` ` ` `// character to _` ` ` `st[i + 1] = ` `'_'` `;` ` ` `// Update the cnt0` ` ` `cnt0--;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Check count of 1's is greater` ` ` `// than the count of 0's` ` ` `if` `(cnt1 > cnt0) {` ` ` `Console.WriteLine(` `"Yes"` `);` ` ` `}` ` ` `else` `{` ` ` `Console.WriteLine(` `"No"` `);` ` ` `}` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `string` `S = ` `"01"` `;` ` ` `int` `N = S.Length;` ` ` `isOnesGreater(S, N);` ` ` `}` `}` `// This code is contributed by ukasp.` |

## Javascript

`<script>` ` ` `// JavaScript Program to implement` ` ` `// the above approach` ` ` `// Function to check whether in a given` ` ` `// binary string can we make number of` ` ` `// 1's greater than the number of 0's` ` ` `// by doing the given operation` ` ` `function` `isOnesGreater(S, N) {` ` ` `// Stores the count of 0's` ` ` `let cnt0 = 0;` ` ` `// Stores the count of 1's` ` ` `let cnt1 = 0;` ` ` `// Traverse through the string S` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `// Check current character is 1` ` ` `if` `(S[i] == ` `'1'` `)` ` ` `// Update cnt1` ` ` `cnt1++;` ` ` `else` ` ` `// Update cnt0` ` ` `cnt0++;` ` ` `}` ` ` `// Traverse through the string S` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `// Check curretn character is 1` ` ` `if` `(S[i] == ` `'1'` `) {` ` ` `// Check if left adjacent` ` ` `// character is 0` ` ` `if` `(i > 0 && S[i - 1] == ` `'0'` `) {` ` ` `// Change the left adjacent` ` ` `// character to _` ` ` `S[i - 1] = ` `'_'` `;` ` ` `// Update the cnt0` ` ` `cnt0--;` ` ` `}` ` ` `// Check if right adjacent` ` ` `// character is 0` ` ` `else` `if` `(i < N && S[i + 1] == ` `'0'` `) {` ` ` `// Change the right adjacent` ` ` `// character to _` ` ` `S[i + 1] = ` `'_'` `;` ` ` `// Update the cnt0` ` ` `cnt0--;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Check count of 1's is greater` ` ` `// than the count of 0's` ` ` `if` `(cnt1 > cnt0) {` ` ` `document.write(` `"Yes"` `);` ` ` `}` ` ` `else` `{` ` ` `document.write(` `"No"` `);` ` ` `}` ` ` `}` ` ` `// Driver Code` ` ` `let S = ` `"01"` `;` ` ` `let N = S.length;` ` ` `isOnesGreater(S, N);` ` ` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output:**

Yes

**Time Complexity:** O(N)**Auxiliary Space:** O(1)