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,
- Set, arr[i] = 1.
- Else If, arr[i – 2], arr[i – 3], arr[i – 4] or arr[i – 5] is 0,
- Set, arr[i] = 1.
- Else,
- Set, arr[i] = 0.
- Increment i by 1 after every iteration.
- If, arr[i / 2], arr[i / 4], arr[i / 3] or arr[i / 5] is 0,
- If arr[N] = 1 then return “Jon”.
- Else return “Arya”.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to return who will winstring divAndSub(int N){ // Edge Case if (N == 1) return "Arya"; if (N < 6) return "Jon"; // Make a dp array of size N+1 int arr[N + 1]; arr[0] = 0; // Initialize the variable int i = 1; // If it's whose turn it is to win on // that move, we'll do 1, otherwise 0 // For 1-5 Jon always win while (i < 6 && i <= N) { arr[i] = 1; i++; } i = 6; while (i <= N) { // Whosever turn will it be we will // check if there is any move by // performing, there is a chance for // him to win, means if any // arr[condition] = 0 then he will win // for sure else not if (arr[i / 2] == 0 || arr[i / 4] == 0 || arr[i / 3] == 0 || arr[i / 5] == 0) { // Means the person doing the move // can win through division arr[i] = 1; } else if (arr[i - 2] == 0 || arr[i - 3] == 0 || arr[i - 4] == 0 || arr[i - 5] == 0) { // Means the person doing the move // can win through subtraction arr[i] = 1; } else { // Else other person will win arr[i] = 0; } i++; } // If arr[N] is 1 then Jon win // else Arya win return arr[N] == 1 ? "Jon" : "Arya";}// Driver Codeint main(){ int N = 3; // Function Call cout << divAndSub(N) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to return who will win public static String divAndSub(int N) { // Edge Case if (N == 1) return "Arya"; if (N < 6) return "Jon"; // Make a dp array of size N+1 int[] arr= new int[N + 1]; arr[0] = 0; // Initialize the variable int i = 1; // If it's whose turn it is to win on // that move, we'll do 1, otherwise 0 // For 1-5 Jon always win while (i < 6 && i <= N) { arr[i] = 1; i++; } i = 6; while (i <= N) { // Whosever turn will it be we will // check if there is any move by // performing, there is a chance for // him to win, means if any // arr[condition] = 0 then he will win // for sure else not if (arr[i / 2] == 0 || arr[i / 4] == 0 || arr[i / 3] == 0 || arr[i / 5] == 0) { // Means the person doing the move // can win through division arr[i] = 1; } else if (arr[i - 2] == 0 || arr[i - 3] == 0 || arr[i - 4] == 0 || arr[i - 5] == 0) { // Means the person doing the move // can win through subtraction arr[i] = 1; } else { // Else other person will win arr[i] = 0; } i++; } // If arr[N] is 1 then Jon win // else Arya win return arr[N] == 1 ? "Jon" : "Arya"; }// Driver Codepublic static void main (String[] args) { int N = 3; // Function Call System.out.println(divAndSub(N));}}// This code is contributed by sanjoy_62. |
Python3
# Python code to implement the approach# Function to return who will windef divAndSub(N): if(N == 1): return "Arya" if(N < 6): return "Jon" # make a dp array of size N+1 arr = [0]*(N+1) # Initialize the variable i = 1 # If it's whose turn it is to win on that move, we'll do 1, otherwise 0 # for 1-5 Jon always win while(i < 6 and i <= N): arr[i] = 1 i += 1 i = 6 while(i <= N): # Whosever turn will it be we will # check if there is any move by # performing, there is a chance for # him to win, means if any # arr[condition] = 0 then he will win # for sure else not if(arr[i//2] == 0 or arr[i//4] == 0 or arr[i//3] == 0 or arr[i//5] == 0): # Means the person doing the move can win through division arr[i] = 1 elif(arr[i-2] == 0 or arr[i-3] == 0 or arr[i-4] == 0 or arr[i-5] == 0): # Means the person doing the move can win through subtraction arr[i] = 1 else: # Else other person will win arr[i] = 0 i += 1 # If arr[N] is 1 then Jon win else Arya win return "Jon" if(arr[N] == 1) else "Arya"N = 3# Function callprint(divAndSub(N))# This code is contributed by lokesh. |
C#
// C# implementationusing System;public class GFG{ // Function to return who will win public static string divAndSub(int N) { // Edge Case if (N == 1) return "Arya"; if (N < 6) return "Jon"; // Make a dp array of size N+1 int[] arr= new int[N + 1]; arr[0] = 0; // Initialize the variable int i = 1; // If it's whose turn it is to win on // that move, we'll do 1, otherwise 0 // For 1-5 Jon always win while (i < 6 && i <= N) { arr[i] = 1; i++; } i = 6; while (i <= N) { // Whosever turn will it be we will // check if there is any move by // performing, there is a chance for // him to win, means if any // arr[condition] = 0 then he will win // for sure else not if (arr[i / 2] == 0 || arr[i / 4] == 0 || arr[i / 3] == 0 || arr[i / 5] == 0) { // Means the person doing the move // can win through division arr[i] = 1; } else if (arr[i - 2] == 0 || arr[i - 3] == 0 || arr[i - 4] == 0 || arr[i - 5] == 0) { // Means the person doing the move // can win through subtraction arr[i] = 1; } else { // Else other person will win arr[i] = 0; } i++; } // If arr[N] is 1 then Jon win // else Arya win return arr[N] == 1 ? "Jon" : "Arya"; } static public void Main (){ int N = 3; // Function Call Console.WriteLine(divAndSub(N)); }}// This code is contributed by ksam24000 |
Javascript
// JavaScript code to implement the approach// Function to return who will winconst divAndSub = (N) => { // Edge Case if (N == 1) return "Arya"; if (N < 6) return "Jon"; // Make a dp array of size N+1 let arr = new Array(N + 1).fill(0); arr[0] = 0; // Initialize the variable let i = 1; // If it's whose turn it is to win on // that move, we'll do 1, otherwise 0 // For 1-5 Jon always win while (i < 6 && i <= N) { arr[i] = 1; i++; } i = 6; while (i <= N) { // Whosever turn will it be we will // check if there is any move by // performing, there is a chance for // him to win, means if any // arr[condition] = 0 then he will win // for sure else not if (arr[parseInt(i / 2)] == 0 || arr[parseInt(i / 4)] == 0 || arr[parseInt(i / 3)] == 0 || arr[parseInt(i / 5)] == 0) { // Means the person doing the move // can win through division arr[i] = 1; } else if (arr[i - 2] == 0 || arr[i - 3] == 0 || arr[i - 4] == 0 || arr[i - 5] == 0) { // Means the person doing the move // can win through subtraction arr[i] = 1; } else { // Else other person will win arr[i] = 0; } i++; } // If arr[N] is 1 then Jon win // else Arya win return arr[N] == 1 ? "Jon" : "Arya";}// Driver Codelet N = 3;// Function Callconsole.log(divAndSub(N));// This code is contributed by rakeshsahni |
Output
Jon
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles:
- Introduction to Dynamic Programming – Data Structures and Algorithms Tutorials
- What is memoization? A Complete tutorial
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
