Check If it is Possible to Convert Binary String into Unary String
Given a binary string S of length N. You can apply following operation on S any number of times. Choose two adjacent characters, such that both are 1’s or 0’s. Then invert them, Formally, if both are 0’s then into 1’s or vice-versa. Then your task is to output YES or NO, by checking that using given operations, Is it possible to convert S into either all 0’s or 1’s ?
Examples:
Input: N = 6, S = “110110”
Output: YES
Explanation: The operations are performed as:
- First operation: S1 = 1 and S2 = 1. Both are same, therefore invert them. Then updated S = 000110
- Second operation: S4 = 1 and S5 = 1. Both are same, therefore invert them. Then updated S = 000000
All the string is converted into 0s. Therefore, output is YES. Note that S also can be converted into all 1s by following the sequence: 110110 → 110000 → 110011 → 111111. Both conversions are valid.
Input: N = 7, S = 0101010
Output: NO
Explanation: It can be verified that S can’t be converted into all 1s or 0s by using give operation.
Approach: To Solve this problem follow the below idea
It’s an observation-based problem. It must be observed that, All occurrence of either number (zero or one) must be existed in pair in order to change the entire S to 1 or 0. Let us take some examples:
- 001100 = Possible as both 0 and 1 are occurred in pair.
- 00100 = Possible because 0 occurred in pair.
- 00101 = Not possible as none of the element occurred in pair.
- 1100111 = Possible as 0 occurred in pair
Now, we can use Stack to solve this problem:
- First, we have to create a Stack.
- Iterate on String and follow below steps:
- If stack is empty or peek and current characters are different then put current character into Stack
- Else If current character and peek character of Stack is same, then pop out the peek element from stack.
- If number of elements in stack is either 0 or 1, Then output YES, else NO.
Steps were taken to solve the problem:
- Create a Stack of Character data type let say Stk.
- Iterate over each character of S using loop and follow below mentioned steps under the scope of loop:
- If (Stk is not empty && Peek character == current character)
- Pop out the peek character from Stk
- Else
- Insert character into Stk
- If (Stk is not empty && Peek character == current character)
- If (Size of Stk is less than or equal to 1)
- Output YES
- Else
- Output NO
Below is the code to implement the approach:
C++
// code added by flutterfly #include <iostream> #include <stack> using namespace std; // Function to check the possibility void Is_possible( long long N, string S) { // Initializing Stack stack< char > st; // Iterating over String S for ( char x : S) { // If current and peek characters are same // Then removing that peek element from Stack if (!st.empty() && st.top() == x) { st.pop(); } // Else putting the current character into Stack else st.push(x); } // If there is at max one character in // Stack, Then output YES else NO if (st.size() <= 1) cout << "YES" << endl; else cout << "NO" << endl; } // Driver Function int main() { // Inputs long long N = 6; string S = "110110" ; // Function call Is_possible(N, S); return 0; } |
Java
// Java code to implement te approach import java.util.*; // Driver Class public class GFG { // Driver Function public static void main(String[] args) { // Inputs long N = 6 ; String S = " 110110 "; // Function_call Is_possible(N, S); } // Method to check the possibility public static void Is_possible( long N, String S) { // Initializing Stack Stack<Character> st = new Stack<>(); // Iterating over String S for ( char x : S.toCharArray()) { // If current and peek characters are same // Then removing that peek element from // Stack if (!st.empty() && st.peek() == x) { st.pop(); } // Else putting current character // into Stack else st.push(x); } // If there is at max one character in // Stack, Then output YES else NO if (st.size() <= 1 ) System.out.println("YES"); else System.out.println("NO"); } } |
Python
# code added by flutterfly # Python code to implement the approach # Method to check the possibility def is_possible(N, S): # Initializing Stack st = [] # Iterating over String S for x in S: # If current and peek characters are the same # Then removing that peek element from Stack if st and st[ - 1 ] = = x: st.pop() # Else putting the current character into Stack else : st.append(x) # If there is at max one character in # Stack, Then output YES else NO if len (st) < = 1 : print ( "YES" ) else : print ( "NO" ) # Inputs N = 6 S = "110110" # Function call is_possible(N, S) |
C#
// code added by flutterfly using System; using System.Collections.Generic; public class GFG { // Method to check the possibility public static void Is_possible( long N, string S) { // Initializing Stack Stack< char > st = new Stack< char >(); // Iterating over String S foreach ( char x in S) { // If current and peek characters are the same // Then removing that peek element from Stack if (st.Count > 0 && st.Peek() == x) { st.Pop(); } // Else putting the current character into Stack else { st.Push(x); } } // If there is at max one character in // Stack, Then output YES else NO if (st.Count <= 1) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } // Driver Function public static void Main() { // Inputs long N = 6; string S = "110110" ; // Function call Is_possible(N, S); } } |
Javascript
// JavaScript code added by flutterfly // Method to check the possibility function isPossible(N, S) { // Initializing Stack let st = []; // Iterating over String S for (let x of S) { // If current and peek characters are the same // Then removing that peek element from Stack if (st.length > 0 && st[st.length - 1] === x) { st.pop(); } // Else putting the current character into Stack else { st.push(x); } } // If there is at max one character in // Stack, Then output YES else NO if (st.length <= 1) { console.log( "YES" ); } else { console.log( "NO" ); } } // Inputs let N = 6; let S = "110110" ; // Function call isPossible(N, S); |
YES
Time Complexity: O(N).
Auxiliary Space: O(N).
Contact Us