algoadvance

Leetcode 2660. Determine the Winner of a Bowling Game

Problem Statement

You are given two lists of integers player1 and player2, where each list contains 10 integers that represent the scores that the players have achieved in a single turn of a 10-turn bowling game.

A player is deemed to have gotten a “double score” in a turn if their score during that turn is at least 10. If a player achieves a double score in turn i, then for each of the next two turns, the score from that turn will be doubled.

Return the winner of the game such that:

• 1 indicates player 1 wins.
• 2 indicates player 2 wins.
• 0 indicates a tie.

Clarifying Questions

1. Should we assume that the input lists player1 and player2 always contain exactly 10 integers?
2. Are the scores always non-negative integers?
3. Are there any constraints on the maximum score per turn?

Strategy

1. Parse and iterate through the scores of both players.
2. Track if a player has achieved a double score and then apply the double scores accordingly.
3. Sum the adjusted scores for both players.
4. Compare the final scores and determine the winner.

Code

public class BowlingGameWinner {
    public static int determineWinner(int[] player1, int[] player2) {
        int totalScore1 = calculateTotalScore(player1);
        int totalScore2 = calculateTotalScore(player2);
        
        if (totalScore1 > totalScore2) {
            return 1;
        } else if (totalScore2 > totalScore1) {
            return 2;
        } else {
            return 0;
        }
    }

    private static int calculateTotalScore(int[] player) {
        int score = 0;
        int doubleTurns = 0;

        for (int i = 0; i < 10; i++) {
            if (doubleTurns > 0) {
                score += 2 * player[i];
                doubleTurns--;
            } else {
                score += player[i];
            }
            
            if (player[i] >= 10) {
                doubleTurns = 2;
            }
        }
        
        return score;
    }

    public static void main(String[] args) {
        int[] player1 = {10, 2, 3, 10, 5, 7, 3, 2, 8, 4};
        int[] player2 = {2, 10, 10, 8, 8, 9, 1, 6, 6, 3};
        
        System.out.println(determineWinner(player1, player2));  // Should print 2
    }
}

Time Complexity

• The time complexity for calculating the total score for both players is O(n), where n is the number of turns, since we are iterating through the list of scores of each player.
• In this case, n is always 10, so the complexity is effectively O(1) for calculating each player’s score and a total of O(1) for the entire function.

Thus, the overall time complexity is O(1).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?