You are given an arr[] of distinct positive integers along with an integer X (X ? 1). arr[] contains only 1 and all possible powers of prime number such that every element of arr[] is at most X. Two players A and B are playing a game on integer X alternatively. In each turn, one can choose a number arr[i] from arr[] such that arr[i] ? X and update X to X – arr[i]. The game goes on until X becomes 0. The task is to find the winner if A starts first and both play optimally.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 7}, X = 7
Output: A
Explanation: Player A choose arr[5] = 7 from the arr[] and update X to 7 – 7 = 0.
Therefore, A wins the game because B can’t make any move on 0.Input: arr[] = {1}, X = 1
Output: A
Explanation: Player A choose arr[0] = 1 from the arr[] and update X to 1 – 1 = 0.
Therefore, A wins the game because B can’t make any move on 0.
Approach: Implement the idea below to solve the problem
if X % 6 = 0. Then, player B wins else player A wins.
Proof of the approach:
Let’s see the cases for X = [1, 2, 3, . . . ., 7]
For X = 1: arr[] will be: {1}
- Player A can subtract 1 from X .So, that X becomes 0 and player B can’t make any move on X further.Therefore, player A wins.
For X = 2: arr[] will be: {1, 2}
- Player A can subtract 2 from X .So, that X becomes 0 and player B can’t make any move on X further.Therefore, player A wins.
For X = 3: arr[] will be: {1, 2, 3}
- Player A can subtract 3 from X .So, that X becomes 0 and player B can’t make any move on X further.Therefore, player A wins.
For X = 4: arr[] will be: {1, 2, 3, 4}
- Player A can subtract 4 from X .So, that X becomes 0 and player B can’t make any move on X further.Therefore, player A wins.
For X = 5: arr[] will be: {1, 2, 3, 4, 5}
- Player A can subtract 5 from X .So, that X becomes 0 and player B can’t make any move on X further.Therefore, player A wins.
For X = 6: arr[] will be: {1, 2, 3, 4, 5}
- Player A loses here.
All possible cases:
- (i) Player A makes X as = (6-1) = 5, Player B can directly subtract 5.Hence B wins.
- (ii) Player A makes X as = (6-2) = 4, Player B can directly subtract 4.Hence B wins.
- (iii) Player A makes X as = (6-3) = 3, Player B can directly subtract 3.Hence B wins.
- (iv) Player A makes X as = (6-4) = 2, Player B can directly subtract 2.Hence B wins.
- (v) Player A makes X as = (6-5) = 1, Player B can directly subtract 1.Hence B wins.
In all above cases it can be verified that there is no such move possible so that A can be winner of the game.
For X = 7: arr[] will be: {1, 2, 3, 4, 5, 7}
- Player A can subtract 7 from X .So, that X becomes 0 and player B can’t make any move on X further.Therefore, player A wins.
- Till, Now We observe a pattern that if X is a multiple of 6, Then B wins else A wins.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>using namespace std;// Function which is called in main()string Find_Winner(int X){ // Checking if X is a multiple of 6 if (X % 6 == 0) { return "B"; } // If X is not a multiple of 6 else { return "A"; }}int main(){ int X = 7; int arr[] = { 1, 2, 3, 4, 5, 7 }; // Function call cout << Find_Winner(X); return 0;}// This code is contributed by akashish__ |
Java
// Java code to implement the approach:import java.io.*;class GFG { // Driver Function public static void main(String[] args) { int X = 7; int[] arr = { 1, 2, 3, 4, 5, 7 }; // Function call System.out.println(Find_Winner(X)); } // Function which is called in main() static String Find_Winner(int X) { // Checking if X is a multiple of 6 if (X % 6 == 0) { return "B"; } // If X is not a multiple of 6 else { return "A"; } }} |
Python3
# python3 code to implement the approach:# Function which is called in main()def Find_Winner(X): # Checking if X is a multiple of 6 if (X % 6 == 0): return "B" # If X is not a multiple of 6 else: return "A"# Driver Functionif __name__ == "__main__": X = 7 arr = [1, 2, 3, 4, 5, 7] # Function call print(Find_Winner(X)) # This code is contributed by rakeshsahni |
C#
// C# code to implement the above approach:using System;public class GFG { // Driver Function public static void Main(string[] args) { int X = 7; int[] arr = { 1, 2, 3, 4, 5, 7 }; // Function call Console.WriteLine(Find_Winner(X)); } // Function which is called in main() static string Find_Winner(int X) { // Checking if X is a multiple of 6 if (X % 6 == 0) { return "B"; } // If X is not a multiple of 6 else { return "A"; } }}// This code is contributed by AnkThon |
Javascript
// Javascript code to implement the approach:// Driver Functionlet X = 7;let arr = [1, 2, 3, 4, 5, 7]// Function callconsole.log(Find_Winner(X));// Function which is called in main()function Find_Winner(X) { // Checking if X is a multiple of 6 if (X % 6 == 0) { return "B"; } // If X is not a multiple of 6 else { return "A"; }}// This code is contributed saurabh_jaiswal. |
A
Time Complexity: O(1)
Auxiliary Space: O(1)
