You are given a number

`$N >= 10`

.Write a script to split the given number such that the difference between two consecutive numbers is always

`1`

and it shouldn't have leading`0`

.Print the given number if it impossible to split the number.

`Input: $N = 1234 Output: 1,2,3,4 Input: $N = 91011 Output: 9,10,11 Input: $N = 10203 Output: 10203 as it is impossible to split satisfying the conditions.`

This is pretty simple to solve. Once we have a starting number `N`

, it's
easy to process throught the list:

- Check if the string starts with the number; if not, we have a failure.
- Else, remove
`N`

from the beginning of the string, and recurse with`N + 1`

and the remainder of the string; if this fails, recurse with`N - 1`

and the remainder of the string. If this fails as well, the entire match fails.

We're the left with picking the starting number. There are only a few possible starting numbers: each of the prefixes of the string.

It's not hard to see the running time is linear in the lenght of the
string. Going into recursion twice has the appearance of an exponential
time algorithm, but it's impossible for a string to start with both
`N + 1`

and `N - 1`

— at least one of the recursive calls has to
terminate immediately.

First, we create a subroutine `make_sequence`

. It gets two arguments,
`$string`

, the string we have to turn into a sequence, and `$start`

, the
number the sequence should start with. If we can make a sequence, we return
an array with the chunks (in reverse order — this is because it's more
efficient to repeatedly push to an array than to unshift). If we cannot
make a sequence, we return undef.

In particular, if the starting number equals the whole string, we return an one element array with that starting number:

```
sub make_sequence ($string, $start) {
if ($string eq $start) {
return [$start]
}
if (index ($string, $start) == 0) {
my $tail = substr $string, length $start;
my $rest;
if (($rest = make_sequence ($tail, $start + 1)) ||
($rest = make_sequence ($tail, $start - 1))) {
push @$rest => $start;
return $rest;
}
}
return;
}
```

Now it's a matter of calling this method with each of the possible
prefixes of the given input (which we have in `$_`

): we can stop
and print the result the first time we get an defined result:

```
for my $i (1 .. length) {
#
# Try to make a sequence with each possible start.
#
my $result = make_sequence $_, substr $_, 0, $i;
if ($result) {
say join "," => reverse @$result;
last;
}
}
```

Note that we always find a sequence — in the worst case, it's a one element sequence equal to the entire string. And this is exactly what we should print if no sequence can be made.

Find the full program on GitHub.

We have similar implementations in AWK, Bash, Lua, Node.js, Python and Ruby.