Perfect Squares Leetcode


#1

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

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

Example 2:

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

#2

We use BFS to identify the min number of levels we would deep dive to sum with all squares.

class Solution {
    public int numSquares(int n) {
        if(n<2) return n;
        int sqRoot = (int) Math.sqrt(n);
        boolean[] visited = new boolean[n];
        int[] sqrs = new int[sqRoot];
        for(int i = 1; i <= sqRoot; ++i) sqrs[i-1] = i * i;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        int level = 0;
        while(!queue.isEmpty()){
            level++;
            int size = queue.size();
            for(int i=0;i<size;i++){
                int num = queue.poll();
                for(int sqr : sqrs){
                    int remain = num-sqr;
                    if(remain==0) return level;
                    else if(remain > 0 && !visited[remain-1]){
                        visited[remain-1] = true;
                        queue.offer(remain);
                    } else if(remain < 0) break;
                }
            }
        }
        return 0;
    }
}