# Codingame Solution: Number staircase

## Goal

A number staircase s is an integer number that, when read from left to right, starts with the number 1, which may be followed by a 2, which may be followed by a 3, and so on. This process continues until a maximum number n is reached, which may contain more than one digit. From this point on, the number staircase s will descend starting at n – 1, then n – 2, then n – 3, and so on, until it descends back to 1.

For example, the number 123456789101110987654321 is a number staircase.

Check whether a given number is a number staircase.
Input
An integer string s
Output
true if s is a number staircase, false otherwise
Constraints
$$s\in\mathbb{N}$$ where $$s\leq10^{10000}$$

## Solution

If the number $$s$$ consists of only one digit numbers, the maximum string length can be 17; 9 up and 8 down. The length in this case must be odd!

If the number consists of up to two-digit numbers, the maximum string length can be 376; 9 one-digit numbers up and down plus 90 two-digit numbers up and at most 89 two-digit numbers down. All these numbers must be even!

When we formalize these findings to come up with intervals we need to check, we can say

$$[1, 17]$$, as $$1\cdot 9 + 1\cdot 8$$
$$[18, 376]$$, as $$1\cdot 9 + 2\cdot 90 +2\cdot 89 + 1\cdot 9$$
$$[377, 5775]$$, as $$1\cdot 9 + 2\cdot 90 +3\cdot 900 + 3\cdot 899 +2\cdot 90 + 1\cdot 9$$

As the maximum string length can be 10000, we can treat every other number as a number with 4 digit numbers in it. Having these four cases allows us to formulate an equation, expressing the mid number of each range. That means we're looking for a number $$m$$, which is $$1\dots 10\dots 100\dots m\dots 100\dots 10\dots 1$$, in this example for 3-digit numbers in the middle.

Case 1 $$(L\leq 17)$$:

$$m = \frac{(L - 1) - 1}{2} + 1$$

Case 2 $$(L\leq 376)$$:

$$m = \frac{(L - 18)/2 - 1}{2} + 10$$

Case 3 $$(L\leq 5775)$$:

$$m = \frac{(L - 18 - 360)/3 - 1}{2} + 100$$

Case 4:

$$m = \frac{(L - 18 - 360 - 5400)/4 - 1}{2} + 1000$$

For the general case $$b$$ this means

$$m = \frac{(L - \sigma(b-1))/b - 1}{2} + 10^{b-1} = \frac{L - \sigma(b-1) - b}{2b} + 10^{b-1}$$

The upper-bound of each interval as such is then $$\sigma(b)-b$$, where $$\sigma$$ can be defined as

$\begin{array}{rl} \sigma(b) &= 2(9 + 2\cdot 90 + 3\cdot 900 + \dots + 9b\cdot 10^{b-1})\\ &=18\sum\limits_{i=1}^{b} i\cdot 10^{i-1}\\ &=\frac{2}{9} ((9b-1)\cdot 10^b + 1) \end{array}$

We simplifying the general formula for $$m$$ to get to

$$m=\frac{2 \cdot (10^b - 1) + 9(L-b)}{18b}$$

Knowing $$b$$ allows us to calculate $$m$$ directly, but requires the same case analysis as before. Or we use $$\sigma<L$$! Evalutating this idea doesn't give a closed-form solution though, since $$x\cdot 10^x$$ can't be factored. But since we have a constant upper bound, we can calculate $$m$$ directly and implement the solution like this:

var s = readline();

function validate(s) {

var L = s.length, m, r="";

if (L <= 17) { // σ(1)-1
m = (L + 1) / 2;
} else if (L <= 376) { // σ(2)-2
m = (L + 20) / 4;
} else if (L <= 5775) { // σ(3)-3
m = (L + 219) / 6;
} else { // if (L <= 77774) //  σ(4)-4
m = (L + 2218) / 8;
}

for (i = 1; i <= m; i++)
r+= i;
for (i = m - 1; i > 0; i--)
r+= i;

return s === r;
}

print("" + validate(s));

The trick here is, that we generate a string, exactly as it should be. If the length doesn't match up, $$m$$ will be rubbish and as such the generated string. If it is a valid number, the correct middle element is calculated and the same string is restored as passed as argument.

« Back to problem overview