08.02.2024
279. Perfect Squares medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/499
Problem TLDR
Min square numbers sum up to n
.
Intuition
By wrong intuition would be just subtract maximum possible square number: 12 = 9 + remainder. So, we should explore all of possible squares and choose min count of them. We can do DFS and cache the result. To pass the TLE, we need to rewrite it back into bottom up DP.
Approach
Let’s write as shorter as we can by using:
Kotlin:
minOf
,sqrt
withoutMath
,toFloat
vstoDouble
Rust:
(1..)
avoid case of
x = 0
to safely invokeminOf
andunwrap
Complexity
Time complexity:
O(nsqrt(n))Space complexity:
O(n)
Code
fun numSquares(n: Int): Int {
val dp = IntArray(n + 1)
for (x in 1..n)
dp[x] = (1..sqrt(x.toFloat()).toInt())
.minOf { 1 + dp[x - it * it] }
return dp[n]
}
pub fn num_squares(n: i32) -> i32 {
let mut dp = vec![0; n as usize + 1];
for x in 1..=n as usize {
dp[x] = (1..).take_while(|&k| k * k <= x)
.map(|k| 1 + dp[x - k * k]).min().unwrap();
}
dp[n as usize]
}