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.
Examples:
Input: N = 2
Output: 1
Explanation: Tom subtracts 1 from N to make N = 1. Now, Jerry isn’t left with any possible turn so Tom wins the game, and therefore the Output is 1.Input: N = 4
Output: 1
Explanation: 1st turn: Tom subtract 1 from N as 1 is a divisor of 4 and less than 4.
2nd turn: N = 3, Jerry has to subtract 1 as 1 is the only divisor of 3 which is less than 3.
3rd turn: N=2, Tom subtract 1 as 1 is the only divisor of 2 which is less than 2.
4th turn: N = 1, Jerry can’t subtract any value. So, Tom wins.
Approach: To solve the problem follow the below idea:
If the initial value of N is even. Then, the first player can play two types of moves:
- He can subtract 1 since 1 is a divisor of every natural number.
- He can subtract any divisor of N other than 1 and N itself.
The observation is, if N is even, the player who takes the first move, wins, else the second player wins.
Below are the steps for the above approach:
- Check if N is even, return 1, and print “Tom Wins” else, return 0, and print “Jerry Wins”.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;int numsGame(int N){ // Check if N is even or not if (N % 2 == 0) // If even then tom wins return 1; // Otherwise jerry wins return 0;}// Drivers codeint main(){ int n = 8; if (numsGame(n) == 1) cout << "Tom Wins"; else cout << "Jerry Wins"; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { public static int numsGame(int N) { // Check if N is even or not if (N % 2 == 0) { // If even then Tom wins return 1; } // Otherwise Jerry wins return 0;}// Drivers codepublic static void main(String[] args) { int n = 8; if (numsGame(n) == 1) System.out.println("Tom Wins"); else System.out.println("Jerry Wins");}}//This code is given by Shivam Miglani |
Python3
# Python code for the above approachdef numsGame(N): # Check if N is even or not if (N % 2 == 0): # If even then tom wins return 1 # Otherwise jerry wins return 0# Drivers coden = 8if (numsGame(n) == 1): print("Tom Wins")else: print("Jerry Wins")# This code is contributed by Susobhan Akhuli |
C#
using System;public class Program { public static int numsGame(int N) { // Check if N is even or not if (N % 2 == 0) { // If even then tom wins return 1; } // Otherwise jerry wins return 0; } public static void Main() { int n = 8; if (numsGame(n) == 1) { Console.WriteLine("Tom Wins"); } else { Console.WriteLine("Jerry Wins"); } }} |
Javascript
<script>// JavaScript Code:function numsGame(N) { // Check if N is even or not if (N % 2 == 0) { // If even then Tom wins return 1; } // Otherwise Jerry wins return 0;}let n = 8;if (numsGame(n) == 1) document.write("Tom Wins");else document.write("Jerry Wins");</script> |
Tom Wins
Time complexity: O(1) // since no loop or recursion is used the algorithm takes up constant time to perform the operations
Auxiliary space: O(1) as no space is required
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
