Perl Weekly Challenge 138: Split Number

Input: $n = 81
Output: 1

Input: $n = 9801
Output: 1

Input: $n = 36
Output: 0

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 (<>) {
    chomp;
    say $_ > 1 && can_split (sqrt ($_), $_) ? 1 : 0
}

Find the full program on GitHub.