Problem Description
Given two integer arrays, player1 and player2, where each element represents the number of pins hit in a turn of a bowling game, compute each player's score according to the following rules:
- For the iᵗʰ turn, if in either of the previous two turns (i-1 or i-2) the player hit all 10 pins, then the value for the current turn is doubled (2*xᵢ); otherwise, it remains xᵢ. Calculate the total score for each player and return:
- 1 if player1 wins,
- 2 if player2 wins,
- 0 if the game is a draw.
Key Insights
- The game is turn-based, and each turn's score might be doubled if the player achieved a perfect hit (10 pins) in either of the previous two turns.
- It’s efficient to iterate over the turns once for each player while checking the last one or two turns when available.
- Boundary checks for the first and second turn are necessary since there might not be two previous turns at the beginning.
Space and Time Complexity
Time Complexity: O(n) - where n is the number of turns, as each player's turns are processed in a single pass. Space Complexity: O(1) - additional storage is limited to a few variables for tracking scores and indices.
Solution
The solution involves iterating over both players' scores simultaneously (or separately). For each turn:
- Check if the previous one or two turns exist and if either of them had 10 pins knocked down.
- If so, double the current turn's pins; otherwise, use the pin count as it is.
- Sum these turn scores to determine the total score for each player.
- Finally, compare the scores and return 1 if player1’s score is higher, 2 if player2’s score is higher, or 0 if they are equal.
The primary data structures used here are arrays (or lists) for storing the pins knocked down each turn and simple integer variables for score accumulations. The algorithm is a straightforward simulation of the turn-by-turn game rules.