tags: leetcode medium Math Dynamic Programming Breadth-First Search

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.

Examples

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 \leq n \leq 10^4$

Code

#define MIN(x, y) x<y ? x : y

int numSquares(int n){
    int *result = malloc((n+1) * sizeof(int));
    int sqrt_bound = 0;
    for(int num = 0 ; num <= n ; num++){
        result[num] = num;
        sqrt_bound = sqrt(num);
        for(int remain_sqrt = 1 ; remain_sqrt <= sqrt_bound ; remain_sqrt++)
            result[num] = MIN(result[num], result[num-remain_sqrt*remain_sqrt] + 1);
    }
    
    return result[n];
}

Complexity

Space	Time
$O(N)$	$O(N^{3/2})$

Result

• Runtime: 126 ms, faster than 32.80%
• Memory Usage: 8.8 MB, less than 11.83%