# Find the Sums of Perfect Squares in Java

## The challenge

The task is simply stated. Given an integer `n` (`3 < n < 109`), find the length of the smallest list of perfect squares which add up to `n`. Come up with the best algorithm you can; you’ll need it!

Examples:

• `sum_of_squares(17) = 2`
17 = 16 + 1 (4 and 1 are perfect squares).
• `sum_of_squares(15) = 4`
15 = 9 + 4 + 1 + 1. There is no way to represent 15 as the sum of three perfect squares.
• `sum_of_squares(16) = 1`
16 itself is a perfect square.

Time constraints:

5 easy (sample) test cases: `n < 20`

5 harder test cases: `1000 < n < 15000`

5 maximally hard test cases: `5 * 1e8 < n < 1e9`

300 random maximally hard test cases: `1e8 < n < 1e9`

## The solution in Java code

Option 1:

```.wp-block-code{border:0;padding:0}.wp-block-code>div{overflow:auto}.shcb-language{border:0;clip:rect(1px,1px,1px,1px);-webkit-clip-path:inset(50%);clip-path:inset(50%);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;word-wrap:normal;word-break:normal}.hljs{box-sizing:border-box}.hljs.shcb-code-table{display:table;width:100%}.hljs.shcb-code-table>.shcb-loc{color:inherit;display:table-row;width:100%}.hljs.shcb-code-table .shcb-loc>span{display:table-cell}.wp-block-code code.hljs:not(.shcb-wrap-lines){white-space:pre}.wp-block-code code.hljs.shcb-wrap-lines{white-space:pre-wrap}.hljs.shcb-line-numbers{border-spacing:0;counter-reset:line}.hljs.shcb-line-numbers>.shcb-loc{counter-increment:line}.hljs.shcb-line-numbers .shcb-loc>span{padding-left:.75em}.hljs.shcb-line-numbers .shcb-loc::before{border-right:1px solid #ddd;content:counter(line);display:table-cell;padding:0 .75em;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;white-space:nowrap;width:1%}```import java.lang.Math;
import java.util.*;
public class SumOfSquares {

public static int nSquaresFor(int n) {
if(Math.sqrt(n)%1==0) return 1;
while(n % 4 == 0)  n /= 4;
if(n % 8 == 7) return 4;
for(int i = 0; i*i < n; ++i) {
int a = n - i*i;
if(Math.sqrt(a)%1==0) return 2;
}
return 3;
}
}
```Code language: Java (java)```

Option 2:

``````public class SumOfSquares {

public static int nSquaresFor(int n) {
if (Math.sqrt(n) % 1 == 0) {
return 1;
}
for (int t = 1; t * t <= n; t++) {
if (Math.sqrt(n - t * t) % 1 == 0) {
return 2;
}
}
while (n % 4 == 0) {
n /= 4;
}
if(n%8 == 7) {return 4;}

return 3;
}
}
```Code language: Java (java)```

Option 3:

``````import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SumOfSquares {
public static int nSquaresFor(int n) {
List<Integer> counts = new ArrayList<>();
int end = (int) Math.floor(Math.sqrt(n));
if (end*end == n){
return 1;
}
for (int start = 1; start < end; start++) {
int sum = start*start;
int s = n - start*start;
int count = 1;
while (sum != n) {
int p = (int) Math.floor(Math.sqrt(s));
sum += p * p;
s = n - sum;
count++;
}
counts.add(count);
}
return counts.stream().min(Integer::compareTo).get();
}
}
```Code language: Java (java)```

## Test cases to validate our solution

``````import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

public class SolutionTest {

@Test
public void easyTests() {
assertEquals(4, SumOfSquares.nSquaresFor(15));
assertEquals(1, SumOfSquares.nSquaresFor(16));
assertEquals(2, SumOfSquares.nSquaresFor(17));
assertEquals(2, SumOfSquares.nSquaresFor(18));
assertEquals(3, SumOfSquares.nSquaresFor(19));
}
}
```Code language: Java (java)```
Tags:
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments