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

Snakes And Ladders Problem

LeetCode 909. You are given an n x n integer...

Rotting Oranges Problem

LeetCode 994. You are given an m x n grid...

Numbers With Same Consecutive Differences Problem

LeetCode 967. Return all non-negative integers of length n such...

K-Similar Strings Problem

LeetCode 854. Strings s1 and s2 are k-similar (for some...