Fastest function to find largest perfect squares of a single number?

Question

I'm attempting to write an algorithm that will find the largest perfect squares of a given integer, subtracting their values from the total each time, as fast as possible. It's somewhat hard to explain, and I apologize for the somewhat ambiguous title, so I'll give some input/output examples:

---

• Input: 23
• Output: [16, 4, 1, 1, 1]
• Explanation: 25 (5x5) is too large, but 16 (4x4) fits. Add it to the array and subtract 16 from 23 (7). The next largest perfect square that fits is 4 (2x2), so add it to the array and subtract 4 from 7 (3). From here, the largest perfect square is simply 1 (1x1). So add 1 to the array until we've gotten to 0.

---

• Input: 13
• Output: [9, 4]
• Explanation: 9 (3x3) is the largest square, so add it to the array and subtract it from 13 (4). 4 is then also a perfect square, so add it and end there.

---

My solution is as follows (with variable names related to how the question was posed to me):

public static int[] solution(int startingSquareYards) {

        ArrayList<Integer> largestSquares = new ArrayList<Integer>();

        // Cast for use with Math. methods
        double remainingSquareYards = (double) startingSquareYards;

        while (remainingSquareYards > 0) {

            double largestSquareRoot = Math.floor(Math.sqrt(remainingSquareYards));
            
            // Edit - used to be: 
            // double yardsOfMaterialUsed = Math.pow(largestSquareRoot, 2);
            double yardsOfMaterialUsed = largestSquareRoot * largestSquareRoot;

            remainingSquareYards -= yardsOfMaterialUsed;

            largestSquares.add((int) yardsOfMaterialUsed);

        }

        int[] solutionArray = largestSquares.stream().mapToInt(i -> i).toArray();

        return solutionArray;
    }

I'm asking for opinions on my solution and whether I could optimize it in any way for time/space complexity, simplicity (while maintaining easy readability/understanding), etc. It currently works for all of the tests I've written but I may be missing edge cases or places to improve it - the input startingSquareYards can be between 1 and 1,000,000. Any constructive feedback is appreciated :)

Thanks for looking!

Answer 1

As stated in the comments, your exact requirements are not clear. The following code will reproduce the examples of your question. Generally, it will prefer to include the largest square rather than to produce the shortest solution.
E.g. 32 will yield [25, 4, 1, 1, 1] rather than [16, 16]. This seems to be your intention, as your example 23 is expected to yield [16, 4, 1, 1, 1] rather than [9, 9, 4, 1]

private static final BitSet SQUARES = new BitSet(1_000_001);
static { for(int i = 0; i <= 1_000; i++) SQUARES.set(i * i); }

public static int[] solution(int startingSquareYards) {
    IntStream.Builder b = IntStream.builder();
    for(int square; startingSquareYards > 0; startingSquareYards -= square) {
        square = SQUARES.previousSetBit(startingSquareYards);
        b.add(square);
    }
    return b.build().toArray();
}

It’s designed to handle your specified input numbers between 1 and 1,000,000.

It simply prepares a BitSet telling which integer number is a square, which allows quickly finding the largest square number equal or smaller than a value. It’s a linear search, but a search that can process 64 numbers at a time with a cheap integer operation. This avoids any expensive floating point operation. It also has no boxing to Integer objects.