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