Solution

Method 1 – Dynamic Programming (Game Theory)

Intuition

This is a classic take-away game. For each number of stones, we check if there is a move (removing a square number) that leaves the opponent in a losing position. If so, the current player can win.

Approach

Let dp[i] be true if the current player can win with i stones.
For each i, try all possible square numbers k*k <= i. If there is any dp[i - k*k] == false, then dp[i] = true.
The answer is dp[n].

Code

[{"language":"C++","code":"class Solution {\npublic:\n    bool winnerSquareGame(int n) {\n        vector<bool> dp(n+1, false);\n        for (int i = 1; i <= n; ++i) {\n            for (int k = 1; k*k <= i; ++k) {\n                if (!dp[i - k*k]) {\n                    dp[i] = true;\n                    break;\n                }\n            }\n        }\n        return dp[n];\n    }\n};","lang":"cpp"},{"language":"Go","code":"func winnerSquareGame(n int) bool {\n    dp := make([]bool, n+1)\n    for i := 1; i <= n; i++ {\n        for k := 1; k*k <= i; k++ {\n            if !dp[i-k*k] {\n                dp[i] = true\n                break\n            }\n        }\n    }\n    return dp[n]\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public boolean winnerSquareGame(int n) {\n        boolean[] dp = new boolean[n+1];\n        for (int i = 1; i <= n; ++i) {\n            for (int k = 1; k*k <= i; ++k) {\n                if (!dp[i - k*k]) {\n                    dp[i] = true;\n                    break;\n                }\n            }\n        }\n        return dp[n];\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun winnerSquareGame(n: Int): Boolean {\n        val dp = BooleanArray(n+1)\n        for (i in 1..n) {\n            for (k in 1..Math.sqrt(i.toDouble()).toInt()) {\n                if (!dp[i - k*k]) {\n                    dp[i] = true\n                    break\n                }\n            }\n        }\n        return dp[n]\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def winnerSquareGame(self, n: int) -> bool:\n        dp = [False] * (n+1)\n        for i in range(1, n+1):\n            k = 1\n            while k*k <= i:\n                if not dp[i - k*k]:\n                    dp[i] = True\n                    break\n                k += 1\n        return dp[n]","lang":"python"},{"language":"Rust","code":"impl Solution {\n    pub fn winner_square_game(n: i32) -> bool {\n        let n = n as usize;\n        let mut dp = vec![false; n+1];\n        for i in 1..=n {\n            let mut k = 1;\n            while k*k <= i {\n                if !dp[i - k*k] {\n                    dp[i] = true;\n                    break;\n                }\n                k += 1;\n            }\n        }\n        dp[n]\n    }\n}","lang":"rust"},{"language":"TypeScript","code":"class Solution {\n    winnerSquareGame(n: number): boolean {\n        const dp = Array(n+1).fill(false);\n        for (let i = 1; i <= n; i++) {\n            for (let k = 1; k*k <= i; k++) {\n                if (!dp[i - k*k]) {\n                    dp[i] = true;\n                    break;\n                }\n            }\n        }\n        return dp[n];\n    }\n}","lang":"typescript"}]

Complexity

⏰ Time complexity: O(n*sqrt(n)) where n is the number of stones.
🧺 Space complexity: O(n) for the DP array.

8:["$","div",null,{"className":"max-w-7xl mx-auto px-4 py-8","children":[["$","header",null,{"className":"mb-8 pb-4","children":[["$","div",null,{"className":"flex flex-wra

Related Tags