ksandeep.v2
BAN USER
Comments (3)
Reputation 50
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
5
of 5 vote
Let us define a function is_first_player_winner() which returns 1 if the first player can control the game and force a win. This function returns 0 if the first player cannot do so, and consequently the second player wins.
Now, we can think of a recursive solution. If we want to find out if the first player can force a win for a given value if "N", we can consider all possible combinations of the first two moves.
We can divide N by the product of the first two moves and then apply the same function recursively to check if player 1 can force a win (Optimal substructure).
Based on the answer of these subproblems, we can check if player 1 can force a win or not.
// Recursive Solution
int is_first_player_winner (int n)
{
/* Returns 1 if Player_1 can control and win the game
Returns 0 if the Player_1 cannot control and win the game */
if ( n <= 1 )
{
// should not reach here
// exit
}
if (n > 2 && n <= 9)
return 1; // first player wins
if (n > 9 && n <= 18)
return 0; // first player cannot win
/* Consider the first two moves in the game
They can be one of the following: (2,2), (2,9), (9,2), (9,9) */
// case 2,2
int win_2_2 = is_first_player_winner (ceil((float)n/4));
// case 2,9 or 9,2
int win_2_9 = is_first_player_winner (ceil((float)n/18));
// case 9,9
int win_9_9 = is_first_player_winner (ceil((float)n/81));
if ((win_2_2 && win_2_9)  (win_9_9 && win_2_9))
return 1;
else
return 0;
}

ksandeep.v2
September 24, 2012 Comment hidden because of low score. Click to expand.
0
of 0 vote
Random( )  generates either a 0 or a 1.
 ksandeep.v2 January 31, 2012Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
What is the general rule? The preprocessing time is accounted for in the algorithm's complexity ? Or it is treated as a onetime overhead ?
 ksandeep.v2 September 25, 2012