News Leaflets
A leading news portal.

Find winner of game where in each move division of N or subtraction is done

0 10

Improve Article

Save Article

Like Article

Improve Article

Save Article

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 <bits/stdc++.h>

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:

FOLLOW US ON GOOGLE NEWS

Read original article here

Denial of responsibility! News Leaflets is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.
Leave a comment