A and B are playing a game. In the beginning, there are n coins. Given two more numbers x and y. In each move, a player can pick x or y or 1 coin. A always starts the game. The player who picks the last coin wins the game or the person who is not able to pick any coin loses the game. For a given value of n, find whether A will win the game or not if both are playing optimally.
Examples:Â
Input : n = 5, x = 3, y = 4 Output : A There are 5 coins, every player can pick 1 or 3 or 4 coins on his/her turn. A can win by picking 3 coins in first chance. Now 2 coins will be left so B will pick one coin and now A can win by picking the last coin. Input : 2 3 4 Output : B
Let us take few example values of n for x = 3, y = 4.Â
n = 0 A can not pick any coin so he lossesÂ
n = 1 A can pick 1 coin and win the gameÂ
n = 2 A can pick only 1 coin. Now B will pick 1 coin and win the gameÂ
n = 3 4 A will win the game by picking 3 or 4 coinsÂ
n = 5, 6 A will choose 3 or 4 coins. Now B will have to choose from 2 coins so A will win.
We can observe that A wins game for n coins only when B loses for coins n-1 or n-x or n-y.Â
C++
// C++ program to find winner of game // if player can pick 1, x, y coins #include <bits/stdc++.h> using namespace std;   // To find winner of game bool findWinner(int x, int y, int n) {     // To store results     int dp[n + 1];       // Initial values     dp[0] = false;     dp[1] = true;       // Computing other values.     for (int i = 2; i <= n; i++) {           // If A losses any of i-1 or i-x         // or i-y game then he will         // definitely win game i         if (i - 1 >= 0 and !dp[i - 1])             dp[i] = true;         else if (i - x >= 0 and !dp[i - x])             dp[i] = true;         else if (i - y >= 0 and !dp[i - y])             dp[i] = true;           // Else A loses game.         else            dp[i] = false;     }       // If dp[n] is true then A will     // game otherwise he losses     return dp[n]; }   // Driver program to test findWinner(); int main() {     int x = 3, y = 4, n = 5;     if (findWinner(x, y, n))         cout << 'A';     else        cout << 'B';       return 0; } |
Java
// Java program to find winner of game // if player can pick 1, x, y coins import java.util.Arrays;   public class GFG {           // To find winner of game     static boolean findWinner(int x, int y, int n)     {         // To store results         boolean[] dp = new boolean[n + 1];                Arrays.fill(dp, false);               // Initial values         dp[0] = false;         dp[1] = true;                // Computing other values.         for (int i = 2; i <= n; i++) {                    // If A losses any of i-1 or i-x             // or i-y game then he will             // definitely win game i             if (i - 1 >= 0 && dp[i - 1] == false)                 dp[i] = true;             else if (i - x >= 0 && dp[i - x] == false)                 dp[i] = true;             else if (i - y >= 0 && dp[i - y] == false)                 dp[i] = true;                    // Else A loses game.             else                dp[i] = false;         }                // If dp[n] is true then A will         // game otherwise he losses         return dp[n];     }            // Driver program to test findWinner();     public static void main(String args[])     {         int x = 3, y = 4, n = 5;         if (findWinner(x, y, n) == true)             System.out.println('A');         else            System.out.println('B');     } } // This code is contributed by Sumit Ghosh |
Python3
# Python3 program to find winner of game # if player can pick 1, x, y coins   # To find winner of game def findWinner(x, y, n):           # To store results     dp = [0 for i in range(n + 1)]       # Initial values     dp[0] = False    dp[1] = True      # Computing other values.     for i in range(2, n + 1):           # If A losses any of i-1 or i-x         # or i-y game then he will         # definitely win game i         if (i - 1 >= 0 and not dp[i - 1]):             dp[i] = True        elif (i - x >= 0 and not dp[i - x]):             dp[i] = True        elif (i - y >= 0 and not dp[i - y]):             dp[i] = True          # Else A loses game.         else:             dp[i] = False      # If dp[n] is true then A will     # game otherwise he losses     return dp[n]   # Driver Code x = 3; y = 4; n = 5if (findWinner(x, y, n)):     print('A') else:     print('B')   # This code is contributed by Azkia Anam |
C#
// C# program to find winner of game // if player can pick 1, x, y coins using System;   public class GFG {           // To find winner of game     static bool findWinner(int x, int y, int n)     {                   // To store results         bool[] dp = new bool[n + 1];               for(int i = 0; i < n+1; i++)             dp[i] =false;               // Initial values         dp[0] = false;         dp[1] = true;               // Computing other values.         for (int i = 2; i <= n; i++)         {                   // If A losses any of i-1 or i-x             // or i-y game then he will             // definitely win game i             if (i - 1 >= 0 && dp[i - 1] == false)                 dp[i] = true;             else if (i - x >= 0 && dp[i - x] == false)                 dp[i] = true;             else if (i - y >= 0 && dp[i - y] == false)                 dp[i] = true;                   // Else A loses game.             else                dp[i] = false;         }               // If dp[n] is true then A will         // game otherwise he losses         return dp[n];     }           // Driver program to test findWinner();     public static void Main()     {         int x = 3, y = 4, n = 5;                   if (findWinner(x, y, n) == true)             Console.WriteLine('A');         else            Console.WriteLine('B');     } }   // This code is contributed by vt_m. |
PHP
<?php // PHP program to find winner of game // if player can pick 1, x, y coins   // To find winner of game function findWinner( $x, $y, $n) {           // To store results     $dp= array();       // Initial values     $dp[0] = false;     $dp[1] = true;       // Computing other values.     for ($i = 2; $i <= $n; $i++)     {           // If A losses any of i-1 or i-x         // or i-y game then he will         // definitely win game i         if ($i - 1 >= 0 and !$dp[$i - 1])             $dp[$i] = true;         else if ($i - $x >= 0 and !$dp[$i - $x])             $dp[$i] = true;         else if ($i - $y >= 0 and !$dp[$i - $y])             $dp[$i] = true;           // Else A loses game.         else            $dp[$i] = false;     }       // If dp[n] is true then A will     // game otherwise he losses     return $dp[$n]; }   // Driver program to test findWinner();     $x = 3; $y = 4; $n = 5;     if (findWinner($x, $y, $n))         echo 'A';     else        echo 'B';           // This code is contributed by anuj_67. ?> |
Javascript
<script>   // Javascript program to find winner of game // if player can pick 1, x, y coins   // To find winner of game function findWinner(x, y, n) {           // To store results     var dp = Array(n + 1).fill(0);       // Initial values     dp[0] = false;     dp[1] = true;       // Computing other values.     for(var i = 2; i <= n; i++)     {                   // If A losses any of i-1 or i-x         // or i-y game then he will         // definitely win game i         if (i - 1 >= 0 && !dp[i - 1])             dp[i] = true;         else if (i - x >= 0 && !dp[i - x])             dp[i] = true;         else if (i - y >= 0 && !dp[i - y])             dp[i] = true;           // Else A loses game.         else            dp[i] = false;     }       // If dp[n] is true then A will     // game otherwise he losses     return dp[n]; }   // Driver code var x = 3, y = 4, n = 5; if (findWinner(x, y, n))     document.write('A'); else    document.write('B');   // This code is contributed by noob2000   </script> |
Output
A
Time Complexity: O(n)
Auxiliary Space: O(n)
This article is contributed by nuclode. If you like neveropen and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
