Find the smallest number of square numbers to create n

An interview question I got -

Given int n, find the smallest number of square numbers that fit inside n.

Example:

Input: 24 
Output: 3 (16 + 4 + 4)

Input: 10
Output: 2 (9 + 1)

Solution:

public class Solution{
    public static int solution(int number){
        int squareCount = 0;
        while(number> 0){
            int square = (int)Math.sqrt(number);
            squareCount++;
            number-=square*square;
        }       
        return squareCount; 
    }
}

Notes:

• Must be Java 7

• Must be in class called Solution, with a public static int solution(int number) method

• Must not use any 3rd party libraries

I like this solution because it is very simple, however it does have one inefficiency. It finds the square root only to perform a squaring operation again. It would be nice if I could find the largest square number in squared form immediately, but I cant think of an efficient way to do this.

Your solution seems to be the most efficient, except for the fact that it doesn't seem to work. You could try finding all possible groups like so:

$$18=4^2+1^2+1^2$$

$$18=3^2+3^2$$

$$18=3^2+2^2+2^2+1^2$$

$$...$$

Then find the smallest group.

Your code would sure like some space. After some nice, wide spacing:

public static int solution(int number) {
    int squareCount = 0;
    while(number > 0){
        int square = (int) Math.sqrt(number);
        squareCount++;
        number -= square * square;
    }       
    return squareCount; 
}

I will post a possible solution after I figure one out.

StackExchange Code Review Q#79871, answer score: 5