# Find the player who will win by choosing a number in range [1, K] with sum total N

Given two integers** K** and **N**, and also given that **Alice** and** Bob** are playing a game. In a single move, a player can choose a number in the range **[1, K]**, and the player whose number makes the total equal to** N** wins the game. Print **Alice** if **Alice** wins the game, else **Bob**, if **Alice **and **Bob **both play the game **alternatively and optimally** and **Alice** starts the game.

**Examples:**

Input:K = 7, N = 8Output:BobExplanation:There is no way for Alice to win the game. When Alice picks any number from 1 to 7 (inclusive both), the opponent wins the game in the next turn by making the total 8 . Suppose you choose number 5, the opponent chooses 3 and wins the game, making the total 5+3=8 .

Input:K = 7, N = 50Output:Alice

**Approach: **This problem can be solved using the concept of Game Theory. Observing the **winning state**.The trick to catch here is that **Alice** can always make a **cycle of (K+1)** repeat, whatever **Bob** chooses .Assume at some point if **Bob** chooses **a**, **Alice **can choose **[(K+1)-a]** keeping the selection within the **range 1 to K** and thus forming a **cycle of (K+1)**.Now, as **Alice** has the first chance, **Alice** should choose * Remainder left on Dividing N by (K+1)* at the Starting so that afterwards she can keep repeating the

**cycle of (K+1)**and achieve the total as

**N**.

Now, the observation is, if

**N%(K+1) is 0**, it is the only case when it’s impossible to win the game for Alice.

Follow the steps given below to solve the problem.

- Check if
**N%(K+1) is 0,**Print**Bob**. - In any other case, Print
**Alice**.

Below is the implementation of the above approach.

## C++14

`// C++ program for above approach` `#include <iostream>` `using` `namespace` `std;` `// Function to predict the winner` `void` `predictTheWinner(` `int` `K, ` `int` `N)` `{` ` ` `if` `(N % (K + 1) == 0)` ` ` `cout << ` `"Bob"` `;` ` ` `else` ` ` `cout << ` `"Alice"` `;` `}` `// Driver Code` `int` `main()` `{` ` ` `// Given Input` ` ` `int` `K = 7, N = 50;` ` ` `// Function call` ` ` `predictTheWinner(K, N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG {` ` ` `// Function to predict the winner` `static` `void` `predictTheWinner(` `int` `K, ` `int` `N)` `{` ` ` `if` `(N % (K + ` `1` `) == ` `0` `)` ` ` `System.out.println( ` `"Bob"` `);` ` ` `else` ` ` `System.out.println(` `"Alice"` `);` `}` `// Driver Code` ` ` `public` `static` `void` `main (String[] args) {` ` ` `// Given Input` ` ` `int` `K = ` `7` `, N = ` `50` `;` ` ` `// Function call` ` ` `predictTheWinner(K, N);` ` ` `}` `}` `// This code is contributed by Potta Lokesh` |

## Python3

`# Python 3 program for above approach` `# Function to predict the winner` `def` `predictTheWinner(K, N):` ` ` `if` `(N ` `%` `(K ` `+` `1` `) ` `=` `=` `0` `):` ` ` `print` `(` `"Bob"` `)` ` ` `else` `:` ` ` `print` `(` `"Alice"` `)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `# Given Input` ` ` `K ` `=` `7` ` ` `N ` `=` `50` ` ` `# Function call` ` ` `predictTheWinner(K, N)` ` ` ` ` `# This code is contributed by SURENDRA_GANGWAR.` |

## C#

`// C# program for the above approach` `using` `System;` `public` `class` `GFG {` ` ` ` ` `// Function to predict the winner` ` ` `static` `void` `predictTheWinner(` `int` `K, ` `int` `N)` ` ` `{` ` ` ` ` `if` `(N % (K + 1) == 0)` ` ` `Console.WriteLine( ` `"Bob"` `);` ` ` `else` ` ` `Console.WriteLine(` `"Alice"` `);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main (` `string` `[] args) {` ` ` `// Given Input` ` ` `int` `K = 7, N = 50;` ` ` `// Function call` ` ` `predictTheWinner(K, N);` ` ` `}` `}` `// This code is contributed by AnkThon` |

## Javascript

`<script>` `// javascript program for above approach` `// Function to predict the winner` `function` `predictTheWinner(K, N)` `{` ` ` `if` `(N % (K + 1) == 0)` ` ` `document.write(` `"Bob"` `);` ` ` `else` ` ` `document.write(` `"Alice"` `);` `}` `// Driver Code` ` ` `// Given Input` ` ` `var` `K = 7, N = 50;` ` ` `// Function call` ` ` `predictTheWinner(K, N);` `// This code is contributed by ipg2016107.` `</script>` |

**Output:**

Alice

**Time Complexity: **O(1)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.