5
\$\begingroup\$

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.

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.