Game of 2/9 (Interview at Facebook)

Question

I was asked this question: similar question at google. Similar question was asked during Facebook interview.

Determine winner of 2/9 number game

Two players play the following game: they pick a random number N (less than 2 billion) then, starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice). Whoever reaches N first wins.

The candidate should write a function that given N decides who wins (first or second player?)

Will a basic random choice of 2/9 for multiplication work or they'd want us to add intelligence in making moves. For ex: start with multiplication with 2 and multiply with 9 only when you see the other person will not be able to reach N quicker than you?

What is the best way to approach these type of questions?

Answer 1

The best approach to this type of questions.

First you need to have the basic understanding of the theory of games. Really basic. That is you are conscious of the fact, that for a given number N there is either a winning strategy for player who starts or a winning strategy for his oponent. So you must assume that they both know the strategy and play the best moves they can.

Then you start to become familiar with the game. You practice on a low level. You quickly notice that for 2-9 the starter is winning, while for 10-18 he must lose. So your function is ready for a case of N<=18.

Then you start thinking of a general winning strategy. Knowing the strategy would give you the algorithm. After 5 minutes (the sooner the better) you understand that you won't fit in time to find the winning strategy, as it is not obvious in that case. So you decide to give the computer some basic principles and let it solve the puzzle for you. You know you'll use the recursion.

You try to find the rule for recursion. You may want to start from the end or from the beginning. I'll describe the approach from the end.

The goal of the game is to push your opponent to the zone, where he must give you the victory. And not get pushed to that zone yourself. From N/9 to N there is a zone for winning. If one is pushed to play from between N/9/2 and N/9, he must lose. (Because both his moves push his opponent to the winning zone.) So you write your function:

wins(n) {
  // returns 1, if starting player is able to reach
  // the range [n, 2*n) with his move
  if (n<=18) {
    if (n<=9)
      return 1;
    else
      return 0;
  } else {
    // I must push him to the zone between N/9/2 and N/9
    return wins(n/18);
  }

If you reached that point, you passed. There are details left, like whether to use float or int, whether to round up or down using int. But in general you showed the right way of thinking and you're ready to face the interviewer :)

EDIT: Actually there is a mistake in the code above. "Winning" is not the same as "being able to reach the range (n,2n)". Maybe 2 functions are necessary here: wins(n) and reaches_slightly_above(n). The latter would be called in a recursive way, and the values returned below 18 should be different, resemble the ones in the solution of Peter de Rivaz. However the solution below and the general approach should be ok.

The alternative approach, going from bottom to up, would be to use the function:

wins(a,n) {
  if (9*a >= n)
    // I win easily
    return 1;
  else
    // if one of my moves pushes the opponent to the zone
    // where he's not able to win, then I win!
    return !wins(2*a, n) || !wins(9*a, n);
}

If they ask for n, you return the value of win(1,n). The complexity of this algorithm is not obvious, but I believe it's logarithmic.

Answer 2

Since they must reach exactly N, this is only possible if N is of the form 2^a * 9^b, with one of a, b allowed to be 0 as well.

Find a and b above: if a + b = even, then the second player will win, otherwise the first will win.

This is because, at each step, a player gets closer to either a or b by one, and therefore to a + b by one. So the problem reduces to: given k, if at each step a player must subtract 1 from k, which player will reach 0 first?