Welcome to Subscribe On Youtube

279. Perfect Squares

Description

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

 

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

 

Constraints:

• 1 <= n <= 104

Solutions

Solution 1

For dynamic programming, define dp[i] to represent the least number of perfect square numbers that sum to i.

Solution 2

This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

• Java
• C++
• Python
• Go
• TypeScript
• Rust

• class Solution {
      public int numSquares(int n) {
          int m = (int) Math.sqrt(n);
          int[] f = new int[n + 1];
          Arrays.fill(f, 1 << 30);
          f[0] = 0;
          for (int i = 1; i <= m; ++i) {
              for (int j = i * i; j <= n; ++j) {
                  f[j] = Math.min(f[j], f[j - i * i] + 1);
              }
          }
          return f[n];
      }
  }
  
  
  // Solution 2
  class Solution {
      public int numSquares(int n) {
          int m = (int) Math.sqrt(n);
          int[] f = new int[n + 1];
          Arrays.fill(f, 1 << 30);
          f[0] = 0;
          for (int i = 1; i <= m; ++i) {
              for (int j = i * i; j <= n; ++j) {
                  f[j] = Math.min(f[j], f[j - i * i] + 1);
              }
          }
          return f[n];
      }
  }
  
  

• class Solution {
  public:
      int numSquares(int n) {
          int m = sqrt(n);
          int f[n + 1];
          memset(f, 0x3f, sizeof(f));
          f[0] = 0;
          for (int i = 1; i <= m; ++i) {
              for (int j = i * i; j <= n; ++j) {
                  f[j] = min(f[j], f[j - i * i] + 1);
              }
          }
          return f[n];
      }
  };
  
  
  // Solution 2
  class Solution {
  public:
      int numSquares(int n) {
          int m = sqrt(n);
          int f[n + 1];
          memset(f, 0x3f, sizeof(f));
          f[0] = 0;
          for (int i = 1; i <= m; ++i) {
              for (int j = i * i; j <= n; ++j) {
                  f[j] = min(f[j], f[j - i * i] + 1);
              }
          }
          return f[n];
      }
  };
  
  

• class Solution:
      def numSquares(self, n: int) -> int:
          m = int(sqrt(n))
          f = [0] + [inf] * n
          for i in range(1, m + 1):
              for j in range(i * i, n + 1):
                  f[j] = min(f[j], f[j - i * i] + 1)
          return f[n]
  
  
  # Solution 2
  class Solution:
      def numSquares(self, n: int) -> int:
          m = int(sqrt(n))
          f = [0] + [inf] * n
          for i in range(1, m + 1):
              for j in range(i * i, n + 1):
                  f[j] = min(f[j], f[j - i * i] + 1)
          return f[n]
  
  

• func numSquares(n int) int {
  	m := int(math.Sqrt(float64(n)))
  	f := make([]int, n+1)
  	for i := range f {
  		f[i] = 1 << 30
  	}
  	f[0] = 0
  	for i := 1; i <= m; i++ {
  		for j := i * i; j <= n; j++ {
  			f[j] = min(f[j], f[j-i*i]+1)
  		}
  	}
  	return f[n]
  }
  
  
  // Solution 2
  func numSquares(n int) int {
  	m := int(math.Sqrt(float64(n)))
  	f := make([]int, n+1)
  	for i := range f {
  		f[i] = 1 << 30
  	}
  	f[0] = 0
  	for i := 1; i <= m; i++ {
  		for j := i * i; j <= n; j++ {
  			f[j] = min(f[j], f[j-i*i]+1)
  		}
  	}
  	return f[n]
  }
  
  

• function numSquares(n: number): number {
      const m = Math.floor(Math.sqrt(n));
      const f: number[] = Array(n + 1).fill(1 << 30);
      f[0] = 0;
      for (let i = 1; i <= m; ++i) {
          for (let j = i * i; j <= n; ++j) {
              f[j] = Math.min(f[j], f[j - i * i] + 1);
          }
      }
      return f[n];
  }
  
  
  // Solution 2
  function numSquares(n: number): number {
      const m = Math.floor(Math.sqrt(n));
      const f: number[] = Array(n + 1).fill(1 << 30);
      f[0] = 0;
      for (let i = 1; i <= m; ++i) {
          for (let j = i * i; j <= n; ++j) {
              f[j] = Math.min(f[j], f[j - i * i] + 1);
          }
      }
      return f[n];
  }
  
  

• impl Solution {
      pub fn num_squares(n: i32) -> i32 {
          let (row, col) = ((n as f32).sqrt().floor() as usize, n as usize);
          let mut dp = vec![vec![i32::MAX; col + 1]; row + 1];
          dp[0][0] = 0;
          for i in 1..=row {
              for j in 0..=col {
                  dp[i][j] = dp[i - 1][j];
                  if j >= i * i {
                      dp[i][j] = std::cmp::min(dp[i][j], dp[i][j - i * i] + 1);
                  }
              }
          }
          dp[row][col]
      }
  }
  
  
  // Solution 2
  impl Solution {
      pub fn num_squares(n: i32) -> i32 {
          let (row, col) = ((n as f32).sqrt().floor() as usize, n as usize);
          let mut dp = vec![i32::MAX; col + 1];
          dp[0] = 0;
          for i in 1..=row {
              for j in i * i..=col {
                  dp[j] = std::cmp::min(dp[j], dp[j - i * i] + 1);
              }
          }
          dp[col]
      }
  }
  
  

All Problems

All Solutions