LeetCode Entry

1510. Stone Game IV

10.08.2026 hard 2026 kotlin rust

Is Alice win Bob taking squares until zero

1510. Stone Game IV hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1447

Problem TLDR

Is Alice win Bob taking squares until zero

Intuition

DFS + memo, iterate over square inside.

Approach

• the zero looses, not the maximum pick

Complexity

• Time complexity: \(O(nsqrt(n))\)

• Space complexity: \(O(n)\)

Code

    val dp = HashMap<Int, Boolean>()
    fun winnerSquareGame(n: Int): Boolean = dp.getOrPut(n) {
        (1..n).takeWhile{it*it<=n}.any{!winnerSquareGame(n-it*it)}
    }

    pub fn winner_square_game(n: i32) -> bool {
        let n = n as usize; let mut d = vec![false; n + 1];
        for i in 1..=n {
            d[i] = (1..).take_while(|&k| k * k <= i).any(|k| !d[i - k * k])
        } d[n]
    }