You are not logged in. Please login at to post your questions!


MCOINS - Coins Game

question-> anyone please share your approach

asked 30 Oct '18, 09:16

sonuexpc_'s gravatar image

accept rate: 0%

Consider only one stack. Let $dp[i]$ store a boolean denoting whether the person whose turn it is will win when there are $i$ coins remaining in the stack.

Following are the base cases:

  1. $i = 0$ : since the person whose chance it is has no coins to take, he/she loses. Hence, $dp[0] = 0$.
  2. $i = 1$ : only one coin, the person whose chance it is can take it and win the game. So, $dp[1] = 1$.
  3. $i = k$ : the person whose chance it is can select all the $k$ coins and win since the other cannot take any more. Hence, $dp[k] = 1$.
  4. $i = l$ : similarly, $dp[l] = 1$.

Now at each turn a person picks either $1$, $k$, or $l$ coins. To win, one would try to take coins in such a way that with the remaining coins the opponent cannot win. In our case, if either of $dp[i-1]$ , $dp[i-k]$ , $dp[i-l]$ is 0 then $dp[i]$ will be $1$ as we can take that may number of coins such that $dp[rem] = 0$ . But if all of $dp[i-1]$ , $dp[i-k]$ , $dp[i-l]$ are $1$ then in all the three possible options, the the game goes to a state where the opponent wins making $dp[i] = 0$ .
Hence, $dp[i]$ = $!(dp[i-1]\&dp[i-k]\&dp[i-l]).$
Here is my code: LINK


answered 01 Dec '18, 01:05

preet_t's gravatar image

accept rate: 0%

edited 14 Jan, 20:33

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 30 Oct '18, 09:16

question was seen: 253 times

last updated: 14 Jan, 20:33