News Leaflets
0 10

Jon and Arya are playing a game. The rules of the game are as follows:

• They have a single number N initially.
• Both will play an alternate move. Jon starts first.
• Both will play each move optimally.
• In each move, they can perform only one of these operations:
• Divide that number by 2, 3, 4, or 5 and take the floor of the result.
• Subtract that number by 2, 3, 4, or 5.
• If after making a move the number becomes 1, the player who made the move automatically loses the game.
• When the number becomes zero, the game will stop and the player who can’t make a move loses the game.

Find the winner of the game.

Examples:

Input: N = 3
Output: Jon
Explanation: Jon will just subtract 3 from initial
number and win the game.

Input: N = 6
Output: Arya
Explanation: If  Jon subtracts any number or divides N, on the next move Arya can subtract any number and make N as 0.

Approach: The problem can be solved using dynamic programming based on the following idea:

As Jon is starting the game, he will try to maximize his chances of winning. So, for any value of i, check if there is any possible value less than i (say j) that ensures Jon’s win, i.e., if j was the initial then the one who starts the game would lose. Then on the first move Jon can move from N to j and ensure his win.

Follow the below steps to solve this problem:

• If N = 1 return “Arya”.
• If N ≤ 5 return “Jon”.
• Make a dp[] array of size N + 1
• Set arr[0] = 0 and i = 1.
• Make arr[i] to min(arr[5], arr[N]) to 1.
• Set i = 6.
• While i ≤ N, whosever turn will it be, check if there is any move by performing which he can win, which means if any arr[condition] = 0 then he will win for sure else not.
• If, arr[i / 2], arr[i / 4], arr[i / 3] or arr[i / 5] is 0,
• Else If, arr[i – 2], arr[i – 3], arr[i – 4] or arr[i – 5] is 0,
• Else,
• Increment i by 1 after every iteration.
• If arr[N] = 1 then return “Jon”.
• Else return “Arya”.

Below is the implementation of the above approach.

## C++

 ` `  `#include ` `using` `namespace` `std;` ` `  `string divAndSub(``int` `N)` `{` `    ` `    ``if` `(N == 1)` `        ``return` `"Arya"``;` ` `  `    ``if` `(N < 6)` `        ``return` `"Jon"``;` ` `  `    ` `    ``int` `arr[N + 1];` `    ``arr[0] = 0;` ` `  `    ` `    ``int` `i = 1;` ` `  `    ` `    ` ` `  `    ` `    ``while` `(i < 6 && i <= N) {` `        ``arr[i] = 1;` ` `  `        ``i++;` `    ``}` ` `  `    ``i = 6;` ` `  `    ``while` `(i <= N) {` ` `  `        ` `        ` `        ` `        ` `        ` `        ` `        ``if` `(arr[i / 2] == 0 || arr[i / 4] == 0` `            ``|| arr[i / 3] == 0 || arr[i / 5] == 0) {` ` `  `            ` `            ` `            ``arr[i] = 1;` `        ``}` ` `  `        ``else` `if` `(arr[i - 2] == 0 || arr[i - 3] == 0` `                 ``|| arr[i - 4] == 0 || arr[i - 5] == 0) {` ` `  `            ` `            ` `            ``arr[i] = 1;` `        ``}` ` `  `        ``else` `{` ` `  `            ` `            ``arr[i] = 0;` `        ``}` ` `  `        ``i++;` `    ``}` ` `  `    ` `    ` `    ``return` `arr[N] == 1 ? ``"Jon"` `: ``"Arya"``;` `}` ` `  `int` `main()` `{` `    ``int` `N = 3;` ` `  `    ` `    ``cout << divAndSub(N) << endl;` ` `  `    ``return` `0;` `}`

Time Complexity: O(N)
Auxiliary Space: O(N)

Related Articles: