# 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**

`s`

**Output**

`s`is a number staircase, false otherwise

**Constraints**

## 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.