algoadvance

Leetcode 3232. Find if Digit Game Can Be Won

Problem Statement

You are given a number represented as a string num. The game starts with Player 1 and Player 2, who take turns. Player 1 moves first. In each turn, a player must remove one digit from the original number. The game ends when only one digit remains. The goal is to determine if the resultant digit is odd or even. If the resultant digit is odd, Player 1 wins; if even, Player 2 wins. Based on optimal play, return true if Player 1 will always win, else return false.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of the string num?
    • Can num contain leading zeros?
  2. Input Format:
    • Should we expect the input to always be valid non-negative integers represented as strings?
  3. Game Rules:
    • When you mention optimal play, should we assume each player will always make the move that maximizes their chances of winning?

Strategy

To solve this problem, we need to break down the game logic with optimal strategy in mind:

  1. Players will remove digits while aiming to maximize their chances.
  2. The game ends with one digit remaining:
    • If the length of num is odd after the last turn, Player 1 wins if the number is odd.
    • If the length of num is even, Player 2 will have made the last move, so Player 2 wins if the number is even.

Steps/Plan:

  1. Traverse the string num and count the frequency of odd and even digits.
  2. From the frequency, deduce whether the remaining digit will be odd or even based on the mechanics of turns.

Code

Here’s the implementation based on the above strategy:

public class DigitGame {

    public boolean isPlayer1Winner(String num) {
        int oddCount = 0;
        int evenCount = 0;

        // Counting odd and even digits
        for (char ch : num.toCharArray()) {
            int digit = ch - '0';
            if (digit % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }

        // Determine the winner based on the turn sequence and digit counts
        if (num.length() % 2 == 1) {
            // Player 1 will have the last move
            return oddCount >= (num.length() + 1) / 2;
        } else {
            // Player 2 will have the last move
            return oddCount > num.length() / 2;
        }
    }

    public static void main(String[] args) {
        DigitGame game = new DigitGame();

        // Example Test Cases
        System.out.println(game.isPlayer1Winner("123")); // true
        System.out.println(game.isPlayer1Winner("222")); // false
        System.out.println(game.isPlayer1Winner("13579")); // true
        System.out.println(game.isPlayer1Winner("2468")); // false
    }
}

Time Complexity

The time complexity of the solution is O(n), where n is the length of the string num. This is because we traverse the string once to count the frequency of odd and even digits. Hence, it is efficient and adheres to linear time complexity.

Feel free to ask any follow-up questions or for further clarification!

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