# O(n)-time O(1)-space C++ solution

• The algorithm is proposed in:

``````https://leetcode.com/discuss/64344/theory-matters-from-backtracking-128ms-to-dp-0ms
``````

Complexities:

• Time: O(n)

• Space: O(1)

C++ Code:

``````bool canWin(string s) {
// Get the primary part of g[n], time complexity O(1)
int NOPERIOD_LAST = 87;
int PERIOD = 34;
vector<int> g(NOPERIOD_LAST, 0);
vector<bool> fmv(NOPERIOD_LAST, true);
for (int idx = 2; idx < NOPERIOD_LAST; ++idx) {
fill_n(fmv.begin(), idx, true);
for (int first = 0, last = idx - 2; first <= last; ++first, --last) {
fmv[g[first] ^ g[last]] = false;
}
g[idx] = find(fmv.begin(), fmv.end(), true) - fmv.begin();
}

// Get g[length of '+...+'] and xor them together: O(n)
int result = 0;
for (string::iterator first = s.begin(); first != s.end(); ++first) {
if (*first == '+') {
// linear search to find the length of successive '+', time O(last-first)
string::iterator last = find(first, s.end(), '-');
size_t dist = last - first;

// calculate g[dist]. Note that the time of for-loop is O(last-first)
for (; dist >= NOPERIOD_LAST; dist -= PERIOD);
result ^= g[dist];

// update first, skip (last-first) entries
if (last == s.end()) {
break;
}
else {
first = last;
}
}
}
return static_cast<bool>(result);
}``````

• What are the magic numbers 34 and 87?

• @maigo The sequence g[n], also shown in https://oeis.org/A215721 , has a period of 34 after its first 87 elements.

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