# Facebook Hacker Cup – Double Squares

*By Luis E. Argote Bolio On January 11, 2011*

Double Squares is the 1st (and the easiest) of the 3 problems posted in the qualification round for the 2011 Facebook Hacker Cup. It consists of calculating how many combinations of adding two squared [integer] numbers equal a given number.

Here’s a copy of the problem description:

**Double Squares**

```
```A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3^2 + 1^2. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 3^2 + 1^2 (we don’t count 1^2 + 3^2 as being different). On the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2.

**Input**

You should first read an integer N, the number of test cases. The next N lines will contain N values of X.

**Constraints**

0 ≤ X ≤ 2147483647

1 ≤ N ≤ 100

**Output**

For each value of X, you should output the number of ways to write X as the sum of two squares.

**Example input**

21

326864818

874566596

1816371419

77068225

1991891221

65

326122507

1041493518

4005625

29641625

3

1257431873

602519112

5928325

25

2147483642

2147483646

415485223

372654318

160225

2147483647

**Example output**

0

1

0

36

1

2

0

0

20

32

0

0

4

24

2

0

0

0

0

12

0

Overall the problem is fairly easy, I solved it using a dynamic programming algorithm in which I make an array with all the squares smaller than the largest possible number and then create two pointers to it, one starting at 0 and the other at the square root of the number to search. I move either of those pointers depending on whether the sum of them is lesser, greater or equal (where I also update a counter) to the number given. This solution is O(n), which is considered very fast.

I initially squandered my opportunity to submit this by (unknowingly) opening the input file before coding the solution. After Facebook decided to allow resubmission, I did so and my solution was accepted.

Anyway, here’s the source code I made:

import java.util.Scanner; /** * @author Luis Edgardo Argote Bolio * This solution is O(n) */ public class Main { public static Scanner in = new Scanner(System.in); public static void main(String[] args) { // This gets the maximum number that can be squared long limit = 2147483647; int maxNumber = (int) Math.sqrt(limit) + 1; long[] squares = new long[maxNumber]; // Calculates the squares for all the relevant numbers < maxNumber // There is no point in exploring other possibilities // This is done once at program startup for (int i = 0; i < maxNumber; i++) { squares[i] = i * i; } int inputs = in.nextInt(); for (int i = 0; i < inputs; i++) { long number = in.nextInt(); // Set the lower pointer at zero to consider all squares from 0 int pos1 = 0; // Set the higher pointer at sqrt(number) to consider all squares up // to number int pos2 = (int) Math.sqrt(number); int count = 0; while (pos1 <= pos2) { if (squares[pos1] + squares[pos2] > number) { // If the sum is lower than the number, increase the right // (higher) number pointer pos2--; } else if (squares[pos1] + squares[pos2] < number) { // If the sum is lower than the number, increase the left // (lower) number pointer pos1++; } else { // Increase the match count count++; // No point in reusing the same numbers as moving only one // pointer will cause the sum to be different from the number pos1++; pos2--; } } System.out.println(count); } } }

### One Response to *Facebook Hacker Cup – Double Squares*

### Leave a Reply Cancel reply

### Categories

- News (2)
- Programming (9)
- Projects (1)
- Reviews (3)

Pure common lisp, tail-recursive solution (without the file reading part):

(defun count-perfect-squares (num min max &optional (accum 0))

(let ((sum (+ (* min min) (* max max))))

(cond (( num sum) (count-perfect-squares num (1+ min) max accum))

(t (count-perfect-squares num min (1- max) accum)))))

(defun num-perfect-squares (num)

(count-perfect-squares num 0 (isqrt num)))