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

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.xxx methods
double remainingSquareYards = (double) startingSquareYards;

while (remainingSquareYards > 0) {

double largestSquareRoot = Math.floor(Math.sqrt(remainingSquareYards));

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 - I feel as though Math.sqrt() can be a bit slow. The input startingSquareYards can be between 1 and 1,000,000. Any constructive feedback is appreciated :)

Thanks for looking!

• I set up commander Lambda's panels only five days ago, did he mess them up again already? Takes at most seven squares, no need to worry about speed I'd say. Nov 6 '21 at 3:42
• @KellyBundy Ha! LAMBCHOP's quantum antimatter reactor core is just too sensitive it seems. They ought to do a better job setting it up, or not assign such a sensitive task to grunts like me! Anything for that promotion - I've got to try to prove to Bunny HQ that I'm worthy! Who knows how far I'll make it though :) Good to hear speed isn't a big deal here. Best of luck to you, fellow double agent! Nov 6 '21 at 4:39
• The HotSpot JVM has intrinsics including for Math.sqrt(). Rather than being a bit slow it should be very fast. Nov 7 '21 at 1:58

## 4 Answers

### A note about Math.sqrt

I feel as though Math.sqrt() can be a bit slow

I thought, since Math.sqrt computes a precise double, maybe if you implement a custom sqrt that computes just up to int precision, it might be an improvement. However, looking at the implementation of Math.sqrt in my IDE I see this comment:

   // Note that hardware sqrt instructions
// frequently can be directly used by JITs
// and should be much faster than doing
// Math.sqrt in software.


Based on this comment in the implementation, I doubt that the optimized less precise custom sqrt implementation could be faster than Math.sqrt.

### Use interface types when possible

For the purposes of largestSquares, any List<Integer> is fine, the specific implementation is not important. So instead of this:

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


Write like this:

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


Note that either way, the <Integer> on the right-hand side can be replaced with <>, because the type is implied.

### Work with int instead of double when possible

Working with double can be tricky sometimes. When an int is enough, it's good to use that instead.

Looking at the implementation, see my comments inline:

// flooring a double
//    -> effectively making it an int
//    -> this can be an int!
//    -> with (int) Math.sqrt(...) instead of flooring
double largestSquareRoot = Math.floor(Math.sqrt(remainingSquareYards));

// the square of an int is an int -> this can be an int
double yardsOfMaterialUsed = largestSquareRoot * largestSquareRoot;

// ... -> actually we never had a good reason to make this not an int...
remainingSquareYards -= yardsOfMaterialUsed;

// ... -> if everything above an int and we no longer need to cast here
largestSquares.add((int) yardsOfMaterialUsed);


Applying the above changes, we can largely avoid double, and the result is a bit simpler:

int remainingSquareYards = startingSquareYards;

while (remainingSquareYards > 0) {
int largestSquareRoot = (int) Math.sqrt(remainingSquareYards);
int yardsOfMaterialUsed = largestSquareRoot * largestSquareRoot;
remainingSquareYards -= yardsOfMaterialUsed;
largestSquares.add(yardsOfMaterialUsed);
}


### Unnecessary explicit cast

The explicit cast here is unnecessary, you can simply omit the (double):

double remainingSquareYards = (double) startingSquareYards;


### Unnecessary local variable

The solutionArray at the end is not useful, I suggest to return its value directly.

I'm no Java guy, but will comment on the "algorithm". You compute and subtract squares all the way until you reach zero. You can get away with doing just one square and very modest amount of precomputation/memory.

Note that squares aren't that far apart. In the allowed range 1 to a million, the largest gap is $$\1000^2-999^2=1999\$$. Consequently, the largest number remaining after subtracting the maximal square is $$\(1000^2-1)-999^2=1998\$$. So you could precompute all answers for up to area 1998 and then always just compute the maximal square and combine it with the stored answer for the remaining area.

Again I'm no Java guy, but here's a Python demo (Try it online!):

from math import isqrt

def solve(area):
square = isqrt(area) ** 2
return [square, *answer[area-square]]

answer = [[]]
for area in range(1, 1999):
answer.append(solve(area))

print(max(map(solve, range(1, 10**6+1)), key=len))


The last line finds a longest answer, output is:

[7056, 144, 16, 4, 1, 1, 1]


So for any allowed input, you never need more than seven squares. Thus if you just want the answer for one input area, even this modest amount of precomputation is very wasteful. But if you want to solve many inputs, like I did when I solved the whole range of a million inputs, it might be worth it. That whole program above btw took about 0.66 seconds.

Since you are subtracting squares, your loop won't have to execute very many times. Every step shrinks the number of yards.

I originally thought you might want to optimize it for when there are multiple values like 1 and 4, but I just did a quick test and for 1 to 10 million you never get more than 7 elements, and 3 of those are 1s.

There will never be more than 3 1s because 4 would take care of that. In fact up to 10 million the only multiples are 1s and 4s. My laptop only took about 4 seconds to calculate all the results up to 10 million in javascript, so I think it's fast enough. If you wanted to do anything you could exit the loop if the remaining is less than 9 and manually check for 4s and then 1s. Just ran a test calculating using each method 5 times for 1-10 million and it didn't help much: 21.5 seconds for the regular method and 19.3 seconds short-circuiting for numbers less than 9.

• Challenge #1: Find out why "In fact up to 10 million the only multiples are 1s and 4s" and rewrite it accordingly. Challenge #2: What's the smallest number that needs 8 squares? Challenge #3: What's the smallest number that needs 9 squares? Nov 7 '21 at 4:12
• Thought about that for a few minutes then gave up :). Thinking about building a square you add one for each row and column and one in the corner to get another square, so that's where you get 3 ones (1+1+1). To get to the next square you add (2+2+1). To get to the next square you add (3+3+1) so you're adding on consecutive odd numbers blocks like 3, 5, 7, 9, 11, 13. So the gaps are increasing linearly and the squares are much bigger than the gaps, but can't put into words (or mat) exactly how that ensures there won't be another duplicate... Nov 7 '21 at 4:31
• In 3 dimensions you could get 7 1s, 3 8s, 2 27s, then never any more. In 4 dimensions you could get 15 1s, 5 16s, 3 81s, 2 256s, and 2 625s before the gap closes... Nov 7 '21 at 4:34
• I think your "There will never be more than 3 1s because 4 would take care of that" puts it well. You can similarly say it for other numbers. Or more "mathematically": If you take a square $n^2$ twice, it contributes $2n^2=(\sqrt{2}n)^2$. When that is $(n+1)^2$ or more, you'd use $(n+1)^2$ instead. Which is when $\sqrt{2}n \ge n+1$, i.e., when $n \ge \frac{1}{\sqrt{2}-1}\approx 2.41$. So you never take the square of $n$ more than once if n is larger than 2, meaning you'd never take a square larger than 4 more than once. Nov 7 '21 at 14:49
• What about challenges #2 and #3? #2 you can do with running your code a little longer, #3 needs a little understanding. Nov 7 '21 at 14:50

An approach to elimitate the Math.sqrt call (which is rather expensive) is using dynamic programming to calculate the squares up until you reach or overshoot the value. Afterwards, you'll have them readily available.

A TreeMap looks like a good data structure as it is navigable:

 // something along the lines of:
TreeMap<Integer, Integer> squareToRoot = ...
int root = 1;
int square;
do {
square = root * root;
squareToRoot.put(square, root);
root++;
} while (square <= destinationValue);



Then, you just have to play around with a https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/NavigableMap.html using some lookups of floor keys and subtraction.

Edit: seemingly Math.sqrt with its native implementation is not a problem, though it was a concern of the original poster, which I addressed in this answer.

Nevertheless: the reaction I got seems to be the new way in a community that I have witnessed going south for quite some years now. Please take this edit as my apology for wasting your time over the last 8 years or so. Codereview will not see me again.

• How expensive is Math.sqrt, and how much faster is your way? Nov 6 '21 at 12:56
• @KellyBundy If you are interested in benchmarking this, please go ahead.
– mtj
Nov 7 '21 at 7:31
• I'd be very happy to. I have benchmark code ready already. All I need is your complete implementation. Nov 7 '21 at 14:51