#2660

Easy

LeetCode Problem Workspace

Determine the Winner of a Bowling Game

Simulate a bowling game to determine the winner based on hit pins per turn for two players.

Problem Statement

You are given two 0-indexed integer arrays player1 and player2. Each element represents the number of pins a player hits in each round of a bowling game. The number of rounds is the same for both players, and each round consists of 10 pins. The goal is to calculate the total score for each player and determine the winner based on the highest score.

The score of a player for each turn is calculated by taking the number of pins they hit, adding a bonus if they hit more than 0 pins. The bonus is double the value of the pins for each round after the first. Compare the final scores of player1 and player2 to determine the winner: output 1 if player1 wins, 2 if player2 wins, or 0 if it’s a tie.

Examples

Example 1

Input: player1 = [5,10,3,2], player2 = [6,5,7,3]

Output: 1

The score of player 1 is 5 + 10 + 2 3 + 2 2 = 25. The score of player 2 is 6 + 5 + 7 + 3 = 21.

Example 2

Input: player1 = [3,5,7,6], player2 = [8,10,10,2]

Output: 2

The score of player 1 is 3 + 5 + 7 + 6 = 21. The score of player 2 is 8 + 10 + 2 10 + 2 2 = 42.

Example 3

Input: player1 = [2,3], player2 = [4,1]

Output: 0

The score of player1 is 2 + 3 = 5. The score of player2 is 4 + 1 = 5.

Constraints

n == player1.length == player2.length
1 <= n <= 1000
0 <= player1[i], player2[i] <= 10

Solution Approach

Score Calculation

Iterate through each turn, calculate the score for each player based on their hit pins and the corresponding bonuses for subsequent rounds.

Comparison of Scores

Once the total scores for both players are computed, compare them to determine the winner. Return 1 if player1 wins, 2 if player2 wins, or 0 if it's a tie.

Efficient Calculation

Ensure the solution runs in linear time by calculating the scores in a single pass through the arrays and comparing the results.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n), where n is the number of turns (the length of the arrays). Each turn is processed in constant time. The space complexity is O(1) since only a few variables are needed to store the cumulative scores.

What Interviewers Usually Probe

Look for understanding of array manipulation and the simulation process.
Ensure that the candidate considers how to apply bonuses correctly in the later rounds.
Check whether the candidate can optimize the solution by calculating the scores in a single pass.

Common Pitfalls or Variants

Common pitfalls

Not properly handling the bonus multiplier for subsequent rounds.
Misinterpreting the problem by assuming that the scores in each round are constant or independent of prior rounds.
Not considering edge cases like a tie or a very small number of rounds.

Follow-up variants

What if the bowling game has a larger number of rounds?
What if the scores for the players are zero for multiple turns?
How would the problem change if the bonus for hitting pins was different?

FAQ

How do you simulate the bowling game in this problem?

Simulate the game by calculating each player's score based on their pin hits per turn and applying the bonus for subsequent rounds.

How can I efficiently calculate the winner in the bowling game?

You can calculate the score of each player in a single pass through the arrays, making the solution O(n) in time complexity.

What is the time complexity of this problem?

The time complexity is O(n), where n is the number of turns, as we process each turn once.

What happens if the scores are equal in the game?

If the scores of both players are equal, the output will be 0, indicating a tie.

Can I apply this pattern to other problems?

Yes, this array plus simulation pattern can be used for problems where step-by-step calculations and comparisons are required, such as games or simulations.

terminal

Solution

Solution 1: Simulation

We can define a function $f(arr)$ to calculate the scores of the two players, denoted as $a$ and $b$, respectively, and then return the answer based on the relationship between $a$ and $b$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def isWinner(self, player1: List[int], player2: List[int]) -> int:
        def f(arr: List[int]) -> int:
            s = 0
            for i, x in enumerate(arr):
                k = 2 if (i and arr[i - 1] == 10) or (i > 1 and arr[i - 2] == 10) else 1
                s += k * x
            return s

        a, b = f(player1), f(player2)
        return 1 if a > b else (2 if b > a else 0)

Continue Practicing

#2679 sum in a matrix #2682 find the losers of the circular game #2717 semi ordered permutation