Perfect Squares Problem


Description

LeetCode Problem 279.

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:

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

Example 2:

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

Constraints:

  • 1 <= n <= 10^4


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int numSquares(int n) {
        vector<int> squares;
        int i = 1;
        while (i*i <= n) {
            squares.push_back(i*i);
            i ++;
        }
        
        queue<int> bfsQ;
        bfsQ.push(n);
        
        int len, curr, threshold = 0;
        int level = 0;
        while (!bfsQ.empty()) {
            len = bfsQ.size();
            for (int i = 0; i < len; i ++) {
                curr = bfsQ.front();
                bfsQ.pop();
                if (curr == 0) 
                    return level;
                threshold = curr / 3;
                for (int j = squares.size() - 1; j >= 0; j --) {
                    if (squares[j] > curr)
                        continue;
                    bfsQ.push(curr - squares[j]);
                    if (squares[j] < threshold)
                        break;
                }
            }
            level ++;
        }
        return level;
    }
};




Related Posts

Average Of Levels In Binary Tree Problem

LeetCode 637. Given the root of a binary tree, return...

Zuma Game Problem

LeetCode 488. You are playing a variation of the game...

Trapping Rain Water II Problem

LeetCode 407. Given an m x n integer matrix heightMap...

Pacific Atlantic Water Flow Problem

LeetCode 417. There is an m x n rectangular island...

N-Ary Tree Level Order Traversal Problem

LeetCode 429. Given an n-ary tree, return the level order...

Minimum Genetic Mutation Problem

LeetCode 433. A gene string can be represented by an...