Find the last remaining Character in the Binary String according to the given conditions | C ++ implementation of the above approach ; Delete counters for each to count the deletes ; Counters to keep track of characters left from each type ; Queue to simulate the process ; Initializing the queue ; Looping till at least 1 digit is left from both the type ; If there is a floating delete for current character we will delete it and move forward otherwise we will increase delete counter for opposite digit ; If 0 are left then answer is 0 else answer is 1 ; Driver Code ; Input String ; Length of String ; Printing answer
#include <bits/stdc++.h> NEW_LINE using namespace std ; string remainingDigit ( string S , int N ) { int del [ ] = { 0 , 0 } ; int count [ ] = { 0 , 0 } ; queue < int > q ; for ( int i = 0 ; i < N ; i ++ ) { int x = S [ i ] == '1' ? 1 : 0 ; count [ x ] ++ ; q . push ( x ) ; } while ( count [ 0 ] > 0 && count [ 1 ] > 0 ) { int t = q . front ( ) ; q . pop ( ) ; if ( del [ t ] > 0 ) { del [ t ] -- ; count [ t ] -- ; } else { del [ t ^ 1 ] ++ ; q . push ( t ) ; } } if ( count [ 0 ] > 0 ) return "0" ; return "1" ; } int main ( ) { string S = "1010100100000" ; int N = S . length ( ) ; cout << remainingDigit ( S , N ) ; }