Robert Eisele
Engineer, Systems Architect and DBA

Codingame: 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.

Go to overview