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++

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