Need Help To Approach a Problem

Tom and Jerry

Easy
Link: Tom and Jerry | Practice | GeeksforGeeks

Problem:
Tom and Jerry being bored in this pandemic, decides to play a game. Given an integer N. On each player’s turn, that player makes a move by subtracting a divisor of current N (which is less than N) from current N, thus forming a new N for the next turn. The player who does not have any divisor left to subtract loses the game.

The game begins with Tom playing the first move. Both Tom and Jerry play optimally. The task is to determine who wins the game. Return 1 if Tom wins, else return 0.

Can anyone please tell how to solve this? The approach or the explanation of the solution.

I’d just brute-force all values of N up to a small limit and look for a pattern: turns out that there’s a very simple one for this Problem :slight_smile:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    const int maxN = 100;
    vector<bool> isWinForPlayer(maxN + 1);
    isWinForPlayer[0] = false; // "0" has no divisor < 0: no moves; player loses.
    isWinForPlayer[1] = false; // "1" has no divisor < 1: no moves; player loses.
    for (int n = 2; n <= maxN; n++)
    {
        bool playerHasWinningMove = false;
        for (int divisor = 1; divisor < n; divisor++)
        {
            if (n % divisor != 0)
                continue;
            if (!isWinForPlayer[n - divisor])
            {
                // Using this divisor forces other player into Losing state.
                playerHasWinningMove = true;
                break;
            }
        }
        isWinForPlayer[n] = playerHasWinningMove;
    }

    for (int n = 1; n <= maxN; n++)
    {
        cout << "n: " << n << " is win for current player? " << isWinForPlayer[n] << endl;
    }
}
3 Likes

Thanks. Nice Approach :+1:
Is there any specific reason why it fits into that pattern or it’s just that way ?

There’s some logic to it. As a hint: if N is even on my turn, then if I simply pick divisor=1 on every subsequent turn, I’ll win no matter what my opponent does.

1 Like