Problem Link:
[CONTEST][1]
[PRACTICE][3]
Author- [Sameer Taneja][4]
Tester- [Vipin Khushu][2]
Editorialist- [Sameer Taneja][4]
Difficulty:
Simple
Prerequisites:
Stack
Problem:
We just have to find out respective string is closed string or not?
Explanation:
As in problem string only consist ‘0’ and ‘1’ i.e. Binary. String is Closed string if counts of ‘0’ and ‘1’ is equal in it.and if for every ‘1’ there is already ‘0’ present in string before it. We use a stack for this problem and do push pop operation on it according to need. Operation as follow:
1.if element in string is ‘0’ than we apply push() operation on it.
2.if element in string is ‘1’ than we check is stack is empty ?:
a) if stack is empty than we break the loop with the help flag and print out “No” as output.as it
is not a great number.
b)if stack is not empty than we apply pop() operation it and repeat the process again until the
end of string.
After traversing the string Now we check is stack is empty or not ?
If it is empty than print “Great number “ else print “No”.
Alternative approach :
We can use two variables a and b for count of ‘0’ and ‘1’ respectively. We also use a flag for great number initialized with 0.if flag equal to 0 than it is great number else not.
We apply a loop on string and apply the following conditions:
If (char==’0’) a++;
Else b++;
Than if(b>a) {flag=1;
break;}
after traversing the string now we check is flag==0 and a==b ? if Yes than it is a great number else not.
Solution:
http://ideone.com/TXCsSt
[1]: Contest Page | CodeChef
[2]: http://www.codechef.com/users/vipinkhushu
[4]: http://www.codechef.com/users/sameer87
[5]: http://www.codechef.com/users/vipinkhushu
[3]: Contest Page | CodeChef