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:

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
guest
0 Comments
Inline Feedbacks
View all comments