Flip Game II

Easy
0/40
Average time to solve is 15m
profile
Contributed by
21 upvotes
Asked in companies
MicrosoftAmazon

Problem statement

Ninja and his friend are playing a game called flip game. They are given a string ‘STR’ containing only two characters, ‘$’ and ‘*.’

In this game, Ninja and his friend take turns to flip two consecutive “$$” to “**”. The flip game ends when Ninja or his friend can no longer make a move, i.e., there is no consecutive “$$” present in the ‘STR’ and, therefore, the other person will be the winner of the game.

Both the players play the game optimally in alternate turns. Given that Ninja starts the game i.e. takes the first turn, your task is to find out if he wins the game.

For example: 
Let 'STR' = "$$**".

There are consecutive "$$" in 'STR' and it is Ninja's turn to begin the game. So, Ninja changes the consecutive "$$" to "**". This changes 'STR' to "****". 

Now, as it is his friend's turn and there are no more consecutive "$$", Ninja wins the game.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first and the only line of each test case contains an input string ‘STR’.
Output Format : 
For each test case, print 'true' if Ninja wins the flip game otherwise print 'false'. 

Print the output of each test case 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’ <= 100
1 <= |’STR’| <= 20
‘STR[i]’ = {‘*’, ‘$’}

Where ‘T’ denotes the total number of test cases, ‘STR’ represents the input string that is given to Ninja and his friend, and |’STR’| represents the length of the string.

Time Limit: 1 second
Sample Input 1:
2
$$$$
****
Sample Output 1:
true
false
Explanation for Sample Output 1:
For sample test case 1: 

In the first move, Ninja changes the string “$$$$” to “$**$”.
Now there is no consecutive “$$” present so Ninja’s friend can not make any move. Hence Ninja wins the game.

For sample test case 2:

There is no consecutive “$$” present so Ninja can not make a move. Hence his friend wins the game.
Sample Input 2:
2
$$$$$
**$$**$
Sample Output 2:
false
true
Explanation for Sample Output 2:
For sample test case 1: 

If the first move, Ninja changes the string “$$$$$” to “**$$$”.
Then his friend changes the string “**$$$” to “****$”.
Now there is no consecutive “$$” present so Ninja can not make any move. Hence his friend wins the game.

For sample test case 2: 

If the first move, Ninja changes the string “**$$**$” to “******$”.
Now there is no consecutive “$$” present so Ninja’s friend can not make any move. Hence Ninja wins the game.
Hint

Think of the backtracing.

Approaches (1)
Backtracking

As we know in our turn we can flip only consecutive “$$” to “**”. So we try to convert every possible consecutive “$$” to “**” and if we win the game then we return true.

 

Here is the algorithm:

  1. If the length of the ‘STR’ is less than 2:
    • Return false.
  2. We run a loop for ‘i‘= 0 to ‘i’ < length of ‘STR’ - 1:
    • If the current character and next character of ‘STR’ is “$”:
      • Change this consecutive “$$” to “**” and store this string in ‘CHANGED_STR’.
      • Call the recursive function canNinjaWin(‘CHANGED_STR’).
      • Now, it is Ninja’s friend’s turn. If he loses the game then Ninja wins.
      • Return true.
  3. Return false.
Time Complexity

O(N ^ N), where ‘N’ represents the length of ‘STR’.

 

The worst-case scenario is when ‘STR’ contains only the “$” character. In this case, at every consecutive index, we are trying to change “$$” to “**” and then calling the same function again to check if this gives us true or not. Hence, the overall time complexity is O(N ^ N). 

Space Complexity

O(N), where ‘N’ represents the length of ‘STR’.

 

The space complexity O(N) is used by the recursive stack space. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Flip Game II
Full screen
Console