We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Stone Game IX

Number: 2156

Difficulty: Medium

Paid? No

Companies: Google, Samsung

Problem Description

Given an array of positive integers representing stone values, two players (Alice and Bob) take turns removing a stone. The cumulative sum of removed stone values is tracked, and the player who makes a move that results in the sum being divisible by 3 loses immediately. If all stones are removed and it is Alice’s turn, Bob wins. Determine if Alice can force a win assuming both players play optimally.

Key Insights

  • Only the stone values modulo 3 affect the running sum modulo 3.
  • Count stones by their remainder when divided by 3: mod0, mod1, and mod2.
  • Stones with a remainder of 0 are “neutral” moves that do not change the sum modulo 3.
  • The win/lose outcome depends on the difference between the counts of mod1 and mod2 stones and the parity (odd or even) of mod0 stones.
  • Managing the order and selection of mod1 and mod2 moves is critical, and the availability of neutral moves (mod0) can flip turn advantages.

Space and Time Complexity

Time Complexity: O(n) – one pass through the stones array is sufficient.
Space Complexity: O(1) – only a fixed number of counters are used.

Solution

The approach is to first count the stones based on their remainder when divided by 3. If there are no mod1 and mod2 stones, then Alice loses by default. For non-trivial cases, check if the difference between the counts of mod1 and mod2 stones is more than 2, which allows Alice to force a winning situation. If the difference is small, then the parity of mod0 stones becomes decisive; if the count of mod0 stones is odd, Alice has an additional advantage. Ultimately, based on these conditions, the solution returns whether Alice can win.

Code Solutions

# Python implementation

def stoneGameIX(stones):
    # Count stones based on remainder modulo 3
    mod0 = mod1 = mod2 = 0
    for stone in stones:
        if stone % 3 == 0:
            mod0 += 1
        elif stone % 3 == 1:
            mod1 += 1
        else:
            mod2 += 1

    # If there are no mod1 and mod2 stones, Alice cannot avoid a loss.
    if mod1 == 0 and mod2 == 0:
        return False

    # If the difference between mod1 and mod2 counts is large, it gives a winning advantage.
    if abs(mod1 - mod2) > 2:
        return True

    # When the difference is small, the parity of mod0 stones is key.
    if mod0 % 2 == 1:
        return True

    return False

# Example usage:
#print(stoneGameIX([2,1]))  # Expected True
#print(stoneGameIX([2]))    # Expected False
← Back to All Questions