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

Whether just trying to meet or meet or exceed N, this can be solved by determining strategies that will always win in various cases. I'll present 5 cases (or 2 cases, the second of which has 4 sub-cases) that cover all N and give the winning strategy for each.

Consider T = ceil( log(N)/log(18) ), that is let T be the smallest power such that 18^T meets or exceeds N.

If 18^(T-1) * 9 < N then the first player always loses to an ideal opponent. Whenever the first player chooses a 2, the second chooses a 9. And whenever the first chooses a 9, the second chooses a 2. In this way, the second player's turn always ends at a power of 18. After T rounds, the second player wins. The first player cannot win at the prior round because multiplying by 9 is not sufficient to exceed N (so neither is multiplying by 2).

So, now let's consider 18^(T-1) * 9 >= N and choose the smallest k such that 18^(T-1) * 2^k > N. There are four possibilities k = 1, 2, 3, or 4.

• (k = 1) First player wins. The first player can start with a 2, and then play as the second player did above, playing the opposite number from the other player each subsequent turn until the next to last round. The second player will always be faced with a power of 18 times the initial 2. At 18^(T-2) * 2, player two can at most reach 18^(T-1) by multiplying by 9, which isn't enough to win, and can at least return 18^(T-2)*4 which player one can multiply by 9 to win with 18^(T-1)*2.

• (k = 3) First player also wins. This time player one starts with a 9 and plays as before. The second player will always be faced with a power of 18 times the initial 9. At 18^(T-2) * 9, player two can at most reach 18^(T-2) * 9 * 9 < 18^(T-2) * 18 * 8 = 18^(T-1) * 2^3, so isn't enough to win, and can at least return 18^(T-1) by multiplying by 2 which player one will multiply by 9 and win.

• (k = 2 or 4) Second player wins. Here the second player should play the opposite number as before, until near the end, so that each round player one starts with a power of 18. At 18^(T-2), player one can at most reach 18^(T-2)* 9 < 18^(T-1), so not enough to win. If he returns 18^(T-2)*9, player two wins with 18^(T-2)*9*9 > 18^(T-2)*18*4 = 18^(T-1)*2^2 If player one instead returns 18^(T-2)*2, player two returns 18^(T-2)*4. Player one can then make at most 18^(T-2)*4*9 = 18^(T-1)*2, which is still not enough. And now player one can at least return 18^(T-2)*8, which is enough for player two to meet the goal since 18^(T-2)*8*9 = 18^(T-1)*4.

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?

Answer 3

There are great answers if N can be divided by 2 and 9, and some good game theory approaches. Here is a simple dynamic programming approach in Javascript to provide the answer for any possible N.

function getWhoWins(n) {
    if(getWhichPlayerWins(0, 1, n) === 0) {
        console.log("First player wins for " + n);
    } else {
        console.log("Second player wins for " + n);
    }
}

// Returns 0 if first, 1 if 2nd player would win
function getWhichPlayerWins(currentPlayer, currentNumber, targetNumber) {
    if(currentNumber * 9 >= targetNumber) {
        return currentPlayer;
    }
    var nextPlayer = (currentPlayer + 1) % 2;
    if(getWhichPlayerWins(nextPlayer, currentNumber *2, targetNumber) === currentPlayer || getWhichPlayerWins(nextPlayer, currentNumber *9, targetNumber) === currentPlayer) {
        return currentPlayer;
    }
    return nextPlayer;
}

The time complexity of this solution is O(2*logN) = O(logN).

Answer 4

Interesting post, and answers. I'd be tempted to propose a theoretical brute force function that enumerates all combinatorial paths using 2/9 factors to N <= 2X10^12 (or as close as possible). I say "theoretical" because I'm assuming that kind of computing power is beyond even FB?

Answer 5

The answer (I'm not 100% sure):

r = N mod 18

if r belongs to (1,9]  player 1 wins
if r belongs to (9,18) or is =1  then player 2 wins.

I don't have a full mathematic demonstration, so I could be wrong.
This should be the correct answer if both players (or at least one of them) know how to play it.

Do I get the job? :)

Answer 6

The optimal play will normally be to play the opposite of the opponent's move except right at the start and end.

By comparing with a recursive solution, it turns out that the answer can be computed based on the most significant digit in a base 18 representation of the number-1 as follows:

def win29(n):
    if n<=9: return True
    n-=1
    while n>=18:
        n = n//18
    return n==1 or 4<=n<=8