Finding minimal "factorization" of an int to square-numbers

Question

The problem I am trying to solve:

Given an int n, return the minimal "factorization" of this int to numbers which are all squares.
We define factorization here not in the usual manner: a factorization of k to m numbers (m1, m2, m3...) will be such that: m1 + m2 + m3 + ... = k.

For example: let n = 12. The optimal solution is: [4,4,4] since 4 is the square of 2 and 4 + 4 + 4 = 12. There is also [9,1,1,1] though it is not minimal since it's 4 numbers instead of 3 in the former.

---

My attempt to solve this:

My idea was given the number n we will perform the following algorithm:
First we will find the closest square number to n (for example if n = 82 we will find 81.
Then we will compute, recursively, the number we got minus the square closest to it.
Here is a flow example: assume n = 12 and our function is f, we compute f(3) UNION {9} and then f(12-4) UNION {4} and then f(12-2) UNION {2}. From each we get a list of square combinations, we take the minimal list from those. We save those in a HashMap to avoid duplications (dynamic-programming style).

Code attempt in Java (incomplete):

public List<Integer> getShortestSquareList(int n){
    HashMap<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>();
    map.put(1, 1);
    List<Integer> squareList = getSquareList(n);
    return internalGetShortestSquareList(n, map, squareList);
}

List<Integer> getSquareList(int n){
    List<Integer> result=new ArrayList<Integer>();
    int i = 1;
    while(i*i <= n){
        result.add(i*i);
        i++;
    }
    return result;
}

public int getClosestSquare(int n,List<Integer> squareList){
    // getting the closestSquareIndex
}

public List<Integer> internalGetShortestSquareList(int n, HashMap<Integer m, HashMap<Integer,List<Integer>> map, List<Integer> squareList){
    if (map.contains(n)) {return map.get(n);}
    int closestSqureIndex=getClosestSquare(m,squareList);
    List<Integer> minSquareList;
    int minSize=Integer.MAX_INT;

    for(int i=closestSqureIndex; i>-1; i--) {
            int square = squareList.get(closestSqureIndex);
            List<Integer> tempSquares= new ArrayList<Integer>(square);
            tempSquares.addAll(f(n-square, map, squareList));

            if (tempSquares.size() < minSize) {
                minSize = tempSize;
                minSquareList = tempSquares;
            }

    }
    map.put(n, minSquareList);       
    return map.get(n);              
}

---

My question:

It seems that my solution is not optimal (imo). I think that the time complexity for my solution is O(n)*O(Sqrt(n)) since the maximal recursion depth is n and the maximum number of children is Sqrt(n). My solution is probably full of bugs - which doesn't matter to me at the moment. I will appreciate any guidance to find a more optimal solution (pseudo-code or otherwise).

Answer 1

Based on @trincot's link, I would suggest a simple O(n sqrt n) algorithm. The idea is :

1. Use exhaustive search on the squares smaller or equal to n to find out if n is a square itself, or a sum of any two or three squares less than n. This can be done in sqrt(n)^3 time, which is O(n sqrt n).
2. If this fails, then find a "factorization" of n in four squares.

To recursively find 4-factorization of a number m, there are three cases now:

1. m is a prime number and m mod 4 = 1. According to the math, we know that n is a product of two squares. Both simple exhaustive search or more "mathy" methods should give an easy answer.
2. m is a prime number and m mod 4 = 3. This case still requires working out the details, but could be implemented using the math described in the link.
3. m is a composite number. This is the recursive case. First factorize m in two factors, i.e. integers u and v so that u*v=m. For performance reasons, they should be as close as possible, but this is a minor detail.

Afterwards, recursively find the 4-factorization of u and v.

Then, using the formula:

(a^2+b^2+c^2+d^2) (A^2+B^2+C^2+D^2) = (aA+bB+cC+dD)^2 + (aB-bA+cD-dC)^2 + (aC-bD-cA+dB)^2 + (aD-dA+bC-cB)^2

find the 4-factorization of m. Here I denoted u = (a^2+b^2+c^2+d^2) and v = (A^2+B^2+C^2+D^2), as their 4-factorization is known at this point.

Answer 2

Much simpler solution:

This is a version of the Coin Change problem. You can call the following method with coins as the list of the square number that smaller than amount (n in your example).

Example: amount=12 , coins={1,2,4,9}

public int coinChange(int[] coins, int amount) {
    int max = amount + 1;             
    int[] dp = new int[amount + 1];  
    Arrays.fill(dp, max);  
    dp[0] = 0;   
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

The complexity of it is O(n*m) where m is the number of coins. So in your example it the same complexity like you mention O(n*sqrt(n)) It solved with Dynamic programming - Bottom up approch. The code has been taken from here.