LeetCode Entry

279. Perfect Squares

08.02.2024 medium 2024 kotlin rust

Min square numbers sum up to n.

279. Perfect Squares medium blog post substack youtube image.png

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 without Math, toFloat vs toDouble
  • Rust: (1..)
  • avoid case of x = 0 to safely invoke minOf and unwrap

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]
  }