Digit Game — Editorial

Opening the reading…

Intuitionthe extra position decides who controls the result

Raze can mark only odd-numbered positions, while Breach can mark only even-numbered positions. Therefore, neither player can remove a position belonging to the other player's group. The game lasts until exactly one position remains, so the only question is which group contains that unavoidable survivor.

When n is odd, there is one more odd-numbered position than even-numbered positions. Breach can mark every even position, while Raze cannot mark all odd positions, so the final position is an odd-numbered one. Raze can choose which odd position to leave, and wins if at least one such digit is odd.

When n is even, the two groups have the same size, but Raze moves one more time because the total number of moves is odd. Raze removes every odd-numbered position, leaving an even-numbered position for the final move. Breach can choose which even position survives, so Breach wins if any even-numbered position contains an even digit.

Approachreduce the game to one parity scan

Compute n from the string length, because the parity of n determines which player controls the final position.

If n is odd, inspect positions 1, 3, 5, and so on, represented by indices 0, 2, 4, and so on; these are the only positions that can survive.

Return 1 as soon as an odd digit appears in an odd-numbered position, because Raze can leave that position unmarked while all even positions are removed.

If no odd-numbered position contains an odd digit, return 2, because every possible survivor for Raze is even.

If n is even, inspect positions 2, 4, 6, and so on, represented by indices 1, 3, 5, and so on; Breach controls which one survives.

Return 2 as soon as an even digit appears in an even-numbered position, because Breach can preserve it and win.

If no even-numbered position contains an even digit, return 1, because every possible even-position survivor is odd.

Complexityone pass and constant working memory

MEASURE	BOUND	WHY
Time	O(n)	The scan visits only one parity group, which contains at most n positions, and each visited character is converted and checked once. It stops early when a winning digit is found, so no position is processed more than once.
Space	O(1) extra	The algorithm stores only n, the loop index, and a few scalar values. The input string is not counted as working memory, and there is no returned collection to exclude; the bound stays constant even in the worst case when the scan reaches its last candidate.

Here n is the length of s.

Annotated solutionC++ · direct parity scan · the complete judge-ready version

CPPCheck only the positions that can contain the final survivor, then return the winner immediately when a decisive digit is found.

#include <string>
using namespace std;

class Solution {
public:
    int digitGame(string s) {
        int n = static_cast<int>(s.size());

        if (n % 2 == 1) {
            for (int i = 0; i < n; i += 2) {
                if ((s[i] - '0') % 2 == 1) {
                    return 1;
                }
            }
            return 2;
        }

        for (int i = 1; i < n; i += 2) {
            if ((s[i] - '0') % 2 == 0) {
                return 2;
            }
        }
        return 1;
    }
};

The loop starts at index 0 for odd n because index 0 represents position 1, an odd-numbered position. It starts at index 1 for even n because index 1 represents position 2, an even-numbered position. The character expression s[i] - '0' converts the decimal character to its numeric digit value, so the parity test matches the winning rule exactly.