Last Updated: 17 Apr, 2021
Andher Nagri
Moderate
Asked in company
As usual in andher nagri, anything can happen as ‘Chaupat Raja’ can take any decision. Now this time he makes a decision regarding voting. So he makes two parties one consisting of ‘Wise’ people and the other consisting of ‘Foolish’ people and voting would take place in the round wise procedure. There were two options in each round and they were allowed to choose one option in each round.
So options are defined as follows:
1. One party people can make another party people lose all his rights in each round.
2. If one person left or we can say the same people left with the right of voting they just can announce the victory.
Your task is to tell which party would win the voting. You were provided with the given string ‘STR’, consisting of characters ‘w’ and ‘f’ where ‘w’ represents the wise people and ‘f’ represents the foolish people and each party plays their best.
Input format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains a single line consisting of the given string ‘STR’
Output Format:
For each test case, print “foolish” if the foolish party wins and “wise” if the wise party wins.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= | STR | <= 5*10^3
STR[i] = [ ‘w’ , ‘f’ ]
Where ‘T’ is the number of test cases, |STR| represents the length of the string and ‘STR’ represents the given string.
Time Limit: 1 sec
Approaches
Approach: The idea here is to store the string characters in a 2-D array and their rights whether they have still rights or blocked from voting. Now we can run a loop for each of the indexes and check if the element at the other index is of the opposite party and we can block him. Now after this we can check in our 2-D array that if still, someone left with the right he is declared as the winner.
Algorithm is as follows:
- So firstly we declare a 2-D array, say ‘ans’ and In this, if the string character is ‘f’ we store ans[i][1] = ‘0’ for that, and if it is ‘w’ we store ans[i][1] = ‘1’ for it.
- Initially, we fiil the ans[i][0] = 0 where we can fill two values ‘0’ represents still have right to vote and ‘1’ represents its right are blocked.
- Now we start iterating our 2-D array and check for each index one by one.
- If any element is found which has the opposite character and still has the right we will block him and break from the loop.
- We repeat the same thing for each of the next elements.
- Now after the iteration we again start iterating the 2-D vector and now we check if what character has left with voting rights so he will be declared as the winner.
- So if in our 2-D array it is found to be ‘1’ we return “wise” else we return “foolish”.
Approach: The idea here is to count the number of foolish people and wise people and for each, we store whether they still have the rights to vote or not and push them in a queue. Now we take the help of queue and if that type of people still has the right to vote we blocked the opposite type of people and decrease its count and we push back the current element in the queue else we pop that element from the queue.
In the end, we check which type of people still has some count that is our winner.
Algorithm is as follows:
- Firstly, we declare a queue and array for storing the count of both party people and an array for storing how many elements are banned.
- Now we store the count of each party’s people and push back all types of characters in the queue.
- Now start iterating until the count of each party's people is greater than ‘1’.
- In every iteration check whether the count of ban type is greater than ‘0’ decreases the ban count by ‘1’ and that element count.
- Else we increase the count of banned people like if the people are of type foolish we increase the count by ‘1’ of banned people in a wise and vice versa also pushed the element in the queue.
- In the end, we check which type of people has still some count or we can say the count is greater than ‘0’ and that is our final answer.