i1300.bashgame.md

1300 · Bash Game

Easy

https://www.lintcode.com/problem/bash-game/description

You are playing the following Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Example

Example 1：

Input：n = 4 
Output：False
Explanation：Take 1, 2 or 3 first, the other party will take the last one

Example 2：

Input：n = 5 
Output：True
Explanation：Take 1 first，Than，we can win the game

Tags

• Dynamic Programming/DP
• Game DP

Company

• Adobe

solution 1 O(n), exceend mem limit (stackoverflow)

class Solution:
    """
    @param n: an integer
    @return: whether you can win the game given the number of stones in the heap
    """
    def can_win_bash(self, n: int) -> bool:
        return self.__memoization({}, n)

    def __memoization(self, memo, n):
        if n <= 3:
            return True
        
        if n in memo:
            return memo[n]

        for i in range(1, 4):
            if not self.__memoization(memo, n-i):
                memo[n] = True
                return memo[n]
        memo[n] = False
        return False 

public class Solution {
    /**
     * @param n: an integer
     * @return: whether you can win the game given the number of stones in the heap
     */
    public boolean canWinBash(int n) {
        HashMap<Integer, Boolean> memo = new HashMap<Integer, Boolean>();
        return this.canWinBashMemoization(n, memo);
    }

    private boolean canWinBashMemoization(int n, HashMap<Integer, Boolean> memo){
        if (n <= 3){
            return true; 
        }

        if (memo.containsKey(n)){
            return memo.get(n);
        }

        for (int i = 1; i <= 3; i++){
            if (!this.canWinBashMemoization(n-i, memo)){
                memo.put(n, true);
                return true;
            }
        }
        memo.put(n, false);
        return false;
    }
}

Solution 2 trick O(1)

public class Solution {
    /**
     * @param n: an integer
     * @return: whether you can win the game given the number of stones in the heap
     */
    public boolean canWinBash(int n) {
        return n % 4 != 0;
    }
}