Perl Weekly Challenge 138: Split Number

by Abigail


You are given a perfect square.

Write a script to figure out if the square root the given number is same as sum of 2 or more splits of the given number.

Example 1

Input: $n = 81
Output: 1

Since, sqrt (81) = 8 + 1.

Example 2

Input: $n = 9801
Output: 1

Since, sqrt (9801) = 98 + 0 + 1.

Example 3

Input: $n = 36
Output: 0

Since, sqrt (36) != 3 + 6.


All our solutions read numbers from standard input (one number per line), and write zeros (if the number cannot be split) and ones (if the number can be split): one result per input number.

We will assume the given numbers are perfect squares, we are not doing any input validation.

We will solve this using recursion.

Let the input number be \(N\), and let \(T = \sqrt{N}\). We can write \[ N = \sum_{i=0}^k b_i \cdot 10^i, 0 \leq b_i < 10, 10^k \leq N < 10^{k+1} \]

Let \(f(T, N)\) be a function which returns \(1\) if \(N\) can be split into parts such that the parts sum to \(T\), and which returns \(0\) otherwise. Then:

\[ f(T, N) = \begin{cases} 1 & \text{if } \begin{cases} T = N, \text {or} \\ \exists j: 0 < j \leq k \wedge f(T - \sum_{i=0}^j b_j \cdot 10^i, \sum_{i=j}^k b_i \cdot 10^{i-j}) \end{cases} \\ 0 & \text{otherwise} \end{cases} \]

We can write \(\sum_{i=0}^j b_j \cdot 10^i\) as \(N \text{mod } 10^j\) and \(\sum_{i=j}^k b_i \cdot 10^{i-j}\) as \(\lfloor \frac{N}{10^j} \rfloor\).

We can easily translate the function \(f\) to code. Note that the requirement of the challenge states that \(N\) must be split into two or more parts; the definition of \(f\) does not account for that. However, the only case for which \(f\) does not split \(N\) into more than one part is the case where \(T = N\). But we have \(T = \sqrt{N}\), and the only solutions for \(N = \sqrt{N}\) are \(N = 0\) and \(N = 1\). We can easily check that condition outside of an implementation of \(f\).


First, a method, can_split, which implements the function \(f\) described above:

sub can_split ($target, $number) {
    return 0 if $target >  $number || $target < 0;
    return 1 if $target == $number;

    my $pow_10 = 10;

    while ($pow_10 <= $number) {
        use integer;
        return 1 if can_split ($target - ($number % $pow_10), 
                                          $number / $pow_10);
        $pow_10 *= 10;

    return 0;

Now, all what needs to be done is read the input, check the input number isn't 0 or 1, and check the return value of can_split:

while (<>) {
    say $_ > 1 && can_split (sqrt ($_), $_) ? 1 : 0

Find the full program on GitHub.

Other languages

We also have implementation in a bunch of different language; they all use the same algorithm as the Perl implementation:

AWK, Bash, bc, C, Go, Java, Lua, Node.js, Pascal, Python, R, Ruby, Scheme, and Tcl.

Please leave any comments as a GitHub issue.