**Difficulty: Medium**

**Frequency: N/A**

Given a positive integer *n*, find the least number of perfect square numbers (for example, `1, 4, 9, 16, ...`

) which sum to *n*.

For example, given *n* = `12`

, return `3`

because `12 = 4 + 4 + 4`

; given *n* = `13`

, return `2`

because `13 = 4 + 9`

.

**My solution:**

**Data structure:**

**Steps:**

**Complexity:**

Runtime:

Space:

**Test cases:**

**Corner cases:**

**Code:**

class Solution { public: int numSquares(int n) { if (n <= 0) return -1; vector<int> countSquares(n + 1, INT_MAX); countSquares[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j * j <= i; j++) { countSquares[i] = min(countSquares[i], countSquares[i - j * j] + 1); } } return countSquares[n]; } };

**Another solution:**

**Data structure:**

**steps:**

**Complexity**:

Runtime:

Space:

**Code**:

**Things to learn:**

Advertisements