Find the smallest number of square numbers to create n

Question

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.

• abl: This solution is incorrect. For input 18 it returns the solution 3 (16 + 1 + 1) while the correct solution is 2 (9 + 9).
• CiaPan: This solution is greedy, so it finds a solution good enough in most cases, but not always the best possible one.

Answer 1

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.

Answer 2

This problem is a variant of the Change-making problem with squares of natural numbers being the available coins denominations—and here is a simple dynamic programming approach.

public static int solution(int number)
{
 int[] termsCount = new int[number + 1];
 int infinity = number + 1; // bigger than any expected result
 termsCount[0] = 0; // done explicitly
 for(int i = 1; i <= number; i ++)
 termsCount[i] = infinity;
 int term;
 for(int i = 1; (term = i*i) <= number; i ++)
 {
 for(int value = term; value <= number; value ++)
 {
 int prevCount = termsCount[value - term];
 if(prevCount != infinity)
 {
 int newCount = prevCount + 1;
 if(newCount < termsCount[value])
 termsCount[value] = newCount;
 }
 }
 }
 return termsCount[number];
}

To solve the problem for some given sum N (the required 'change', represented by a number variable in the code above) and given term/addends values ('coins' denominations) we may create an array of termCounts, which traces how many terms/coins is enough for each sum from 0 to the required N. We will try to add available terms/coins to partial solutions and choose smaller counts (better partial results) when possible.

So we need to initialize the first element of the array with 0 (zero terms is enough to reach a zero sum) and all remaining elements with infinity (so that the first partial solution will be smaller and will be put into the termCounts array).
A minimum possible term/coin value is 1, so the maximum possible solution is N, hence N+1 will do as infinity.

Once the counters are ready we may start adding terms. They have to be squares of natural numbers, so we can enumerate them with term=i*i iterating from i=1. Iteration stops when term exceeds the target N, because a term/coin can't be greater than an intended sum/change (we can't get a sum of 7 with a term 9 in it, can we?).

With each term value we try to use it for each partial result, stored in termCounts. Starting from value equal term (we can't get sum value less than a term) we check a number of terms (a partial solution) for value-term. If it appears non-infinite, which means we have some solution there, we try to extend it by adding our current term: we add 1 to the count and check if the new term/coin count for current value is smaller than what we already have at termCounts[value]. If so, we got a better solution for value, then we store a new count in termCounts.

Note: A no-solution indicator infinite values do not stay long in the solution we consider here. They are overwritten as soon as in the first pass thanks to the first term/coin tested being 1, which allows us to obtain every required sum. Without the 1, however, some sums might remain unreachable with corresponding termCounts elements being infinite. For example, if all the terms/coins available were even, all the odd sums would remain unreachable.
Infinite values also stay temporarily if we start processing terms/coins from bigger values. For example, if we started with term==25 it would fill every 25-th term, and gaps between them would get filled later by lower values/denominations.

This gets iterated across the termsCount array, so we know every solution that can be improved with the new term value gets improved.

Finally every termCounts[value] contains the minimum number of terms from the processed set of perfect squares which make a sum equal value. In particular, the value termsCount[number] returned from the routine is the required answer for the input value number.

Supplement

The first condition in the inner loop is actually not necessary. If the 'previous solution' does not exist yet (that is, prevCount == infinity), then the 'current solution' will appear non-existent, too: newCount = prevCount+1 will be greater than infinity, so it will certainly not satisfy the inner condition, regardless whether the current solution exists or not (is `infinite').

So the inner loop can be safely reduced to:

 for(int value = term; value <= number; value ++)
 {
 int newCount = termsCount[value - term] + 1;
 termsCount[value] = Math.min( termsCount[value], newCount);
 }

Answer 3

An interview without using external libraries is constrained, and it depends on what skills you want to show off. In this case we know that a greedy algorithm will not work, and the answer is 1 to 4 (due to Lagrange's four square theorem).

Thus a fast solution is:

 class Main {
 private static boolean FourSquaresNeeded(int n) {
 // According to https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem
 if (n % 4!=0) return (n % 8) == 7;
 else return FourSquaresNeeded(n / 4);
 }
 public static int solution(int n){
 // Assume that n>0
 // According to https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem 4 is the most, and there's a formula when four is needed
 if (FourSquaresNeeded(n)) return 4;
 // We now know that answer is 1..3
 int nsqrt = (int)Math.sqrt(n); // Truncating
 if (nsqrt * nsqrt == n) return 1;
 // Since it wasn't a square we know that the answer is 2..3, and 2 means a sum of two squares so check that:
 int lower = (int)Math.sqrt(n / 2); 
 // starting from lower (instead of 1 ) avoid double-checking the squares
 for (int i = lower; i <= nsqrt;i++) {
 int restsq = (n - i * i);
 int rest = (int)Math.sqrt(restsq);
 if (rest* rest == restsq) return 2; // A sum of two squares.
 }
 // Not a square, not sum of two squares and not the messy answer requiring 4, so:
 return 3;
 }
 }

Note that it doesn't find the needed squares, just the number of square needed.

Added: If you are good at writing code to factor numbers you could skip the loop and just check the prime-factors of n