You are given a number

`$N >= 10`

.Write a script to find out if the given number

`$N`

is such that sum of squares of all digits is a perfect square. Print`1`

if it is otherwise`0`

.

`Input: $N = 34 Ouput: 1`

\(3^2 + 4^2 = 9 + 16 = 25 = 5^2\)

`Input: $N = 50 Output: 1`

\(5^2 + 0^2 = 25 + 0 = 25 = 5^2\)

`Input: $N = 52 Output: 0`

\(5^2 + 2^2 = 25 + 4 = 29\)

The challenge can be split up into two different tasks: summing the squares of the digits, and determining whether the result is a perfect square or not.

Summing the squares of the digits is straightforward.

We offer four different ways to determine whether the sum of the squares of the digits is a square number. We'll call the sum of the squares of the digits \(S\).

First option is take the square root. We cannot simply check whether the square root is an integer: we're now dealing with floating point numbers. Instead, we round the square root to the nearest integer, square that, and compare that with \(S\). If they're the same, we have a perfect square.

The advantange of this method is that quick. The disadvantage is that we have to deal with floating point numbers. Which means we may have rounding errors.

The second method we offer is to start counting from \(1\), and squaring each number. If we hit \(S\), \(S\) is a perfect square. If we go past \(S\), \(S\) is not a perfect square.

This may sound inefficient, but it's not. If the input has \(N\) digits, then \(S \leq 81 \cdot N\) (if the number contains only \(9\)s). So, we at most have to count till \(9 \sqrt{N}\) before we know whether \(S\) is a perfect square. Even if we have million digits, we at most have to check 9000 numbers. So, the counting part can be done in \(\mathcal{O}(\sqrt{N})\) time, which is less than the \(\mathcal{O}(N)\) which is required to calculate \(S\).

Instead of counting from \(1\), we can start at \(1\) and doubling the number till its square exceeds \(S\). Say, we have doubled \(k\) times, and now we have \(2^{k-1} \leq S < 2^k\). We can now use binary search to find a number \(2^{k-1} \leq l < 2^k\) such that \(l^2 = S\). If such a number exists, \(S\) is a perfect square, else it's not.

Since \(k = \mathcal{O}(\log{\sqrt{N}})\), the running time of this is \(\mathcal{O}(\log{\sqrt{N}})\).

We can precalculate the first 9000 squares. Then, given an \(S\), we can see check whether this is a square by checking it against the precomputed numbers. This is fast, particular if we have many numbers we want to check. The disadvantage is that it doesn't get all the numbers. But the first \(S\) for which this goes wrong is 81,018,001. And a number needs more than 1,000,222 digits before the sum of the squares of its digits can exceed 81,018,001.

We have the input number in `$_`

.

First, calculating the sum of the squares of the numbers:

```
my $sum_of_squares = sum map {$_ * $_} /[1-9]/g;
```

Note that we ignore `0`

s, and the square of `0`

is `0`

.

```
$is_square = $sum_of_squares == int (.5 + sqrt $sum_of_squares) ** 2
```

We'r taking the square root of `$sum_of_squares`

, rounding it to the
nearest integer, squaring that, and comparing it to `$sum_of_squares`

.
If equal, `$sum_of_squares`

is a square, else, it is not.

```
my $root = 0;
$root ++ while $root * $root < $sum_of_squares;
$is_square = $sum_of_squares == $root * $root;
```

We simply count upwards as long as the square of our number is less
thatn `$sum_of_squares`

. Then we check whether we overshot or not:
if we did, it's not a square, else it is.

First, we find a number whose square is larger than `$sum_of_squares`

:

```
my $root_min = 0;
my $root_max = 1;
$root_max *= 2 while $root_max * $root_max < $sum_of_squares;
```

Then we use binary search to zoom into the square root of `$sum_of_squares`

.
Either we hit it (and hence, the square root of `$sum_of_squares`

is an
integer, and thus, `$sum_of_squares`

is a perfect square), or we don't
(and then, `$sum_of_squares`

is not a perfect square):

```
while ($root_min < $root_max) {
my $root_mid = int (($root_min + $root_max) / 2);
my $square_mid = $root_mid * $root_mid;
if ($square_mid == $sum_of_squares) {
$is_square = 1;
last;
}
if ($square_mid < $sum_of_squares) {
$root_min = $root_mid + 1;
}
else {
$root_max = $root_mid;
}
}
```

First, the preprocessing:

```
my %squares = map {$_ * $_ => 1} 1 .. 9000;
```

Then it's just a matter of a lookup:

```
$is_square = $squares {$sum_of_squares};
```

Find the full program on GitHub.

We have implemenations based on the *Taking the square root* method in
AWK, C, Lua, Node.js,
Python and Ruby. And an implemenation based
on *Binary search* in Bash.