# 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.

• This solution is incorrect. For input 18 it returns the solution 3 (16 + 1 + 1) while the correct solution is 2 (9 + 9). – abl Feb 7 '15 at 18:48

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.