Problem Description

You are given two arrays player1 and player2 representing the number of pins knocked down by each player in a bowling game. Each array has n elements, where each element represents the pins knocked down in that turn (maximum 10 pins per turn).

The scoring works with a special bonus rule:

• If a player knocks down 10 pins (a strike) in any turn, then for the next two turns, their points are doubled
• Specifically, for turn i, the score is:
  • 2 * xi if the player got a strike in turn (i-1) OR turn (i-2)
  • xi otherwise (normal scoring)

The total score for each player is the sum of all their turn values after applying the bonus rule.

Your task is to compare the final scores and return:

• 1 if player 1's score is higher
• 2 if player 2's score is higher
• 0 if the scores are tied

For example, if a player's turns are [10, 2, 3]:

• Turn 0: score = 10 (no previous turns, so no bonus)
• Turn 1: score = 2 * 2 = 4 (doubled because of strike in turn 0)
• Turn 2: score = 2 * 3 = 6 (doubled because of strike in turn 0, which is within 2 turns)
• Total score = 10 + 4 + 6 = 20

The solution calculates each player's score by checking the previous two turns for strikes and applying the appropriate multiplier, then compares the final scores to determine the winner.

Intuition

The key insight is that we need to track when strikes (10 pins) occur because they affect scoring for the next two turns. Since the bonus only depends on whether there was a strike in the previous one or two turns, we can process each turn sequentially while looking back.

For each turn i, we only need to check:

• Did turn i-1 have a strike?
• Did turn i-2 have a strike?

If either answer is yes, we double the current turn's score. This is a straightforward simulation - we don't need any complex data structures or algorithms.

The approach becomes clear when we realize:

1. Each turn's score is independent once we know the multiplier (1x or 2x)
2. The multiplier only depends on the previous two turns
3. We can calculate each player's total score independently

Since both players follow the same scoring rules, we can write a single function f(arr) that takes any player's array and returns their total score. The function iterates through each turn, checks if either of the two previous turns was a strike (value of 10), applies the appropriate multiplier (k = 2 if there was a recent strike, otherwise k = 1), and accumulates the score.

Once we have both scores, comparing them is trivial - just return 1, 2, or 0 based on which is larger. The elegance of this solution lies in its simplicity: we're directly simulating the scoring rules without any unnecessary complexity.

Solution Approach

The solution implements a simulation approach by creating a helper function to calculate scores and then comparing them.

Helper Function f(arr):

The core logic resides in the function f(arr) which calculates the total score for a given player's array:

1. Initialize a score accumulator s = 0
2. Iterate through each turn using enumerate(arr) to get both index i and value x
3. For each turn, determine the multiplier k:
   • Check if i > 0 and arr[i-1] == 10 (strike in previous turn)
   • Check if i > 1 and arr[i-2] == 10 (strike two turns ago)
   • If either condition is true, set k = 2, otherwise k = 1
4. Add k * x to the running total s
5. Return the final score s

Main Logic:

1. Calculate player 1's score: a = f(player1)
2. Calculate player 2's score: b = f(player2)
3. Compare scores and return the result:
   • Return 1 if a > b (player 1 wins)
   • Return 2 if b > a (player 2 wins)
   • Return 0 otherwise (tie)

Key Implementation Details:

• The condition (i and arr[i - 1] == 10) is a compact way to check if we're not at index 0 AND the previous turn was a strike
• The condition (i > 1 and arr[i - 2] == 10) ensures we're at least at index 2 before checking two turns back
• The use of the ternary operator k = 2 if ... else 1 cleanly handles the multiplier logic
• The nested ternary in the return statement 1 if a > b else (2 if b > a else 0) elegantly handles all three possible outcomes

The time complexity is O(n) where n is the number of turns, as we iterate through each array once. The space complexity is O(1) as we only use a few variables to track scores.

Example Walkthrough

Let's walk through a small example with player1 = [3, 10, 5, 2] and player2 = [10, 4, 7, 3].

Calculating Player 1's Score:

• Turn 0 (value=3): No previous turns to check for strikes

  • Multiplier k = 1
  • Score = 1 × 3 = 3
  • Running total = 3

• Turn 1 (value=10): Check previous turns

  • Turn 0 had value 3 (not a strike)
  • Multiplier k = 1
  • Score = 1 × 10 = 10
  • Running total = 3 + 10 = 13

• Turn 2 (value=5): Check previous turns

  • Turn 1 had value 10 (strike!) → k should be 2
  • Turn 0 had value 3 (not a strike)
  • Multiplier k = 2 (because of strike in turn 1)
  • Score = 2 × 5 = 10
  • Running total = 13 + 10 = 23

• Turn 3 (value=2): Check previous turns

  • Turn 2 had value 5 (not a strike)
  • Turn 1 had value 10 (strike!) → k should be 2
  • Multiplier k = 2 (because of strike in turn 1, which is 2 turns back)
  • Score = 2 × 2 = 4
  • Running total = 23 + 4 = 27

Calculating Player 2's Score:

• Turn 0 (value=10): No previous turns

  • Multiplier k = 1
  • Score = 1 × 10 = 10
  • Running total = 10

• Turn 1 (value=4): Check previous turns

  • Turn 0 had value 10 (strike!) → k should be 2
  • Multiplier k = 2
  • Score = 2 × 4 = 8
  • Running total = 10 + 8 = 18

• Turn 2 (value=7): Check previous turns

  • Turn 1 had value 4 (not a strike)
  • Turn 0 had value 10 (strike!) → k should be 2
  • Multiplier k = 2 (because of strike in turn 0, which is 2 turns back)
  • Score = 2 × 7 = 14
  • Running total = 18 + 14 = 32

• Turn 3 (value=3): Check previous turns

  • Turn 2 had value 7 (not a strike)
  • Turn 1 had value 4 (not a strike)
  • Multiplier k = 1
  • Score = 1 × 3 = 3
  • Running total = 32 + 3 = 35

Final Comparison:

• Player 1 total: 27
• Player 2 total: 35
• Since 35 > 27, return 2 (Player 2 wins)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the input arrays. The algorithm iterates through each array exactly once in the helper function f(). For each element, it performs constant-time operations (checking previous elements for value 10 and calculating the score). Since the function f() is called twice (once for each player), the total time complexity remains O(n) + O(n) = O(n).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. The variables used include:

• Local variables s, i, x, and k in function f()
• Variables a and b to store the scores All these variables use constant space that doesn't scale with the input size n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Boundary Checking for Previous Turns

A common mistake is not properly checking array boundaries when looking back at previous turns for strikes. Developers might write:

Incorrect Code:

# WRONG - This will cause IndexError or incorrect logic
if arr[i-1] == 10 or arr[i-2] == 10:
    multiplier = 2

Why it's wrong:

• When i = 0, accessing arr[i-1] will incorrectly access the last element (Python's negative indexing)
• When i = 1, accessing arr[i-2] will also incorrectly access from the end of the array

Correct Solution:

has_bonus = False
if i >= 1 and arr[i-1] == 10:
    has_bonus = True
if i >= 2 and arr[i-2] == 10:
    has_bonus = True
multiplier = 2 if has_bonus else 1

2. Using AND Instead of OR Logic

Another pitfall is misunderstanding the bonus condition and checking if BOTH previous turns were strikes:

Incorrect Code:

# WRONG - Requires both turns to be strikes
if i >= 2 and arr[i-1] == 10 and arr[i-2] == 10:
    multiplier = 2

Why it's wrong: The bonus applies if EITHER of the previous two turns was a strike, not if both were strikes.

Correct Solution:

# Check each condition separately with OR logic
if (i >= 1 and arr[i-1] == 10) or (i >= 2 and arr[i-2] == 10):
    multiplier = 2

3. Off-by-One Error in Turn Counting

Some might miscount which previous turns to check:

Incorrect Code:

# WRONG - Checking wrong turns
if i > 0 and arr[i] == 10:  # Checking current turn instead of previous
    multiplier = 2
# OR
if i >= 3 and arr[i-3] == 10:  # Checking too far back
    multiplier = 2

Why it's wrong: The bonus only applies for strikes in turns i-1 and i-2, not the current turn or turns further back.

Correct Solution:

# Only check i-1 and i-2
if (i >= 1 and arr[i-1] == 10) or (i >= 2 and arr[i-2] == 10):
    multiplier = 2

4. Forgetting to Reset or Initialize Variables

When using a flag variable, forgetting to reset it for each turn:

Incorrect Code:

has_bonus = False  # Initialized outside the loop
for i, pins in enumerate(arr):
    if i >= 1 and arr[i-1] == 10:
        has_bonus = True  # Never reset to False
    # ... rest of logic

Why it's wrong: Once has_bonus becomes True, it stays True for all subsequent turns.

Correct Solution:

for i, pins in enumerate(arr):
    has_bonus = False  # Reset for each turn
    if i >= 1 and arr[i-1] == 10:
        has_bonus = True
    if i >= 2 and arr[i-2] == 10:
        has_bonus = True
    multiplier = 2 if has_bonus else 1