# If I'm a interviewer, I prefer the candidates using burte force instead of math method.

• Because it is a "coding interview", not acm/icpc or other competitions. Similar to Josephus Cycle, I prefer LinkedList Cycle than Mod-Method during interviews. Here's a backtraking-dp solution.

``````public class Solution {
public boolean canWinNim(int n) {
if(n>=134882061){//I have no any other ways,please forgive my unchastity(无节操)!
return n%4 != 0;
}
int[] array=new int[n+1];
return dfs(n, array);
}
public boolean dfs(int n,int[] array){
if(array[n]!=0){
return array[n]==1?true:false;
}
if(n<=3){
array[n]=1;
return true;
}else{
for(int i=1;i<=3;i++){
if(!dfs(n-i,array)){
array[n-i]=-1;
array[n]=1;
return true;
}
}
array[n]=-1;
return false;
}
}
}``````

• Agreed. This is not a coding problem anymore, it's a math problem. It doesn't test your coding skills whatsoever.

I was using recursion. It went LTE, but I still preferred it rather than return (n % 4 != 0);

``````public boolean canWinNim(int n) {
return canWinNim(n, 0);
}

public boolean canWinNim(int n, int roundCount) {
roundCount++;
if (n <= 0) {
return false;
} else if (0 < n && n <= 3) {
return (roundCount % 2 == 1);
}

if (roundCount % 2 == 0) {
return (canWinNim(n-1, roundCount)
&& canWinNim(n-2, roundCount)
&& canWinNim(n-3, roundCount));
} else {
return (canWinNim(n-1, roundCount)
|| canWinNim(n-2, roundCount)
|| canWinNim(n-3, roundCount));
}
}``````

• "array[n-i]=-1;" is redundant, "array[n]=-1;" has assigned "-1" already

• I am not a interviewer, however I hold a different opinion, if a problem can be solved with simple algorithm, why shall we implement recursion to make it complicated?

I would rather say this question from my perspective is not suitable for coding interview, but if it does show, n%4 is preferred.

Algorithm matters.

• the second guy win ,the first must be failed. so just return !(win(n-1)or ... or ... ) will be ok.

• Did you solve the 134882061 issue? I use recursion and it give me stack over flow error too...

• memory leak? i would add delete [] array at the end

• Surely if you were an interviewer that wanted to see some dynamic programming or something besides the clever math trick, you would choose a different question, that cannot be solved like this. Why on earth would you penalise someone for a clever solution?

• If it's recursively, i think DP also makes sense:

public class Solution {
public boolean canWinNim(int n) {
if (n <= 3) {
return true;
}
for (int i = 1; i <= 3; i++) {
return !canWinNim(n-i);
}
return false;
}
}

But of course, would be out of memory

• I dont agree. Math is a part of algorithm. So why dont use the best algorithm?

• Why don't we try both way? If I was interviewed with this problem, I will using dp to code and then tell the interviewer I figured out a mathematic method which is more efficient but unusual.

• No matter what you are an interview or a candidate as a problem solver you should always solve a problem in the easiest way. There could be a lot of options to select to solve a problem but I think the easiest human friendly solution should be selected.

• Well, I derived the solution by approaching it as a graph problem, trying to build an algorithm, and the solution ended up being one line :) I think the interviewer will be pleased as long as you demonstrate your thought process.
But I see your point and kind of agree. It's a good practice to try to solve it using DP.
Here's my iterative DP solution, but it's failing with the big input test case, like yours:

``````public class Solution {
public bool CanWinNim(int n)
{
if(n < 4) return true;
if(n == 4) return false;

bool[] dp = new bool[n+1];
dp[1] = true;
dp[2] = true;
dp[3] = true;
dp[4] = false;

for(int i = 5; i <= n; ++i)
{
for(int j = 1; j <= 3; ++j)
{
if(dp[i - j] == false)
{
dp[i] = true;
break;
}
}
}

return dp[n];
}
}
``````

• @lsy1991121 Can u explain OP's soln? I'm not sure I understand it correctly. Thx!

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.