Repository navigation
Expand file tree
/
Copy pathnimGame.cpp
More file actions
72 lines (67 loc) · 2.45 KB
/
Copy pathnimGame.cpp
File metadata and controls
72 lines (67 loc) · 2.45 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// Source : https://leetcode.com/problems/nim-game/
// Author : Calinescu Valentin
// Date : 2015-10-19
/***************************************************************************************
*
* You are playing the following Nim Game with your friend: There is a heap of stones
* on the table, each time one of you take turns to remove 1 to 3 stones. The one who
* removes the last stone will be the winner. You will take the first turn to remove
* the stones.
*
* Both of you are very clever and have optimal strategies for the game. Write a
* function to determine whether you can win the game given the number of stones in the
* heap.
*
* For example, if there are 4 stones in the heap, then you will never win the game: no
* matter 1, 2, or 3 stones you remove, the last stone will always be removed by your
* friend.
*
* If there are 5 stones in the heap, could you figure out a way to remove the stones
* such that you will always be the winner?
*
* Credits:Special thanks to @jianchao.li.fighter for adding this problem and creating
* all test cases.
*
***************************************************************************************/
/*
* Solutions
* =========
*
* Let's look at the example:
*
* 0 stones - false
* 1 stone - true
* 2 stones - true
* 3 stones - true
* 4 stones - false
*
* We notice that all we need for a position to be true is to get the opponent in a position
* that is false. With 1, 2 and 3 you can take 1, 2 and 3 stones respectively to force your
* opponent into having 0 stones, a position where he cannot win. No matter how many stones
* we take from 4 we cannot
*
* force the opponent into a losing positon, so position 4 becomes a losing position.
* Let's take a look at the next 4 positions:
*
* 5 stones - true
* 6 stones - true
* 7 stones - true
* 8 stones - false
*
* With 5, 6 and 7 stones we can take 1, 2 and 3 stones respectively to force the opponent into
* position 4. Position 8 is a losing one because we can only force the opponent into winning
* positions. We notice that this group of 4 positions can repeat itself indefinitely, because
* we only need the previous 3 positions to judge whether a position is winning or losing.
*
* Thus we can see the pattern:
*
* n % 4 == 0 - false
* n % 4 != 0 - true
*
*/
class Solution {
public:
bool canWinNim(int n) {
return !(n % 4 == 0);
}
};