Andher Nagri

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in company
Facebook

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
wff
wfwf

Sample Output 1:

foolish
wise

Explanation For Sample Input 1:

Test Case 1: 
For the first test case given string is ‘wff’ so first starting from ‘wise’ people he first bans the rights of the next foolish people, then foolish people ban the right of ‘wise’ people now only one ‘foolish’ candidate remains with the right of voting so in the next round he declares his victory.

Test Case 2:
For the second test case given string is ‘wfwf’ so first starting from ‘wise’ people he first bans the right of the next ‘foolish’ people then the next ‘wise’ people ban the right of the next ‘foolish’ people and in the second round only wise people remain with right of voting so wise people declared their victory.

Sample Input 2:

1
wfw

Sample Output 2:

wise

Explanation For Sample Input 2:

Test Case 1: 
For the first test case given string is ‘wfw’ so first starting from ‘wise’ people he first bans the rights of the next foolish people, then wise people remain so they declare their victory.
Hint

Can you think of a 2-d array for storing information?

Approaches (2)
Brute Force Approach

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: 

  1. 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.
  2. 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.
  3. 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.
  4. We repeat the same thing for each of the next elements.
  5. 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.
  6. So if in our 2-D array it is found to be ‘1’ we return “wise” else we return “foolish”.
Time Complexity

O(N ^ 2), where ‘N’ represents the size of the string.

 

As for each index, we are traversing the whole array so we have to run two nested loops which make the complexity O(N ^ 2).

Space Complexity

O(N), where ‘N’ represents the size of the string.

 

As we are using a 2-D array that takes space equal to O(N).

Code Solution
(100% EXP penalty)
Andher Nagri
Full screen
Console