Skip to content

Instantly share code, notes, and snippets.

@progheal

progheal/Truly_Random.md

Last active July 11, 2016 03:43
Show Gist options
  • Save progheal/22a8cbd8226d951b222454aad080f260 to your computer and use it in GitHub Desktop.
Save progheal/22a8cbd8226d951b222454aad080f260 to your computer and use it in GitHub Desktop.
Download ZIP
The solution of Truly_Random challenge: https://codefights.com/challenge/WFRx6HvmG5KLABepG/main
Raw
Truly_Random.md

Let's analyze all these digits. We classify the appearing position within the number it begins, with the rightmost being 1. For example, the 111 in 41118 is said to be at position 4, while the cross-number 777 between 72977 and 72978 is said to be at position 2. The input size is n.

000

Because 000 cannot cross number (no number starts with 0), the position of 000 is at least 3. For position p, the other digits of the number can be combined to count them; for example, numbers for n=5 and p=4 are 10000, 10001, 10002, ..., 90009, 100000; there are 100 - 10 + 1 = 91 of them.

It is easy to deduct that there's 10^{n-3}-10^{p-3}+1 ways to have 000 in position p. Adds up all of these for p from 3 to n, we have
(n-2)\times10^{n-3}-\sum_{p=3}^n 10^{p-3}+(n-2)=(n-2)\times10^{n-3}-\underset{n-2}{\underbrace{111\dots1}}+(n-2)

111 through 888

These cases are similar, so below use only 111 for illustration.

For positions 3 through n, there are 10^{n-3} for each position; the digits outside pattern counts them, similar to the case of 000, except that we can now have "leading zeroes" (that is discarded anyway). As a comparison, for n=5 and p=4 the numbers are 1110, 1111, 1112, ..., 1119, 11110, 11111, 11112, ..., 91119, a total of 100 of them.

For position 2, all numbers begin with 1 and ends with 11 is counted. Consider the number of digits between them: there can be -1 digits (11; the beginning 1 overlaps the ending 11, hence -1), 0 digits (111), 1 digits (1011 through 1911), etc. until n-3 digits (10...011 through 19...911). The total count is thus
1+\sum_{d=0}^{n-3} 10^d=1+\underset{n-2}{\underbrace{111\dots1}}
For example, for n=5 and p=2 these numbers are counted: 11(12); 111(112); 1011(1012), 1111(1112), 1211(1212), through 1911(1912); 10011(10012), 10111(10112), 10211(10212), through 19911(19912); a total of 1+111=112 numbers.

For position 1, similar counting happens for numbers begin with 11 and ends with 1, except there's no case for -1 digits between head and tail (11 is followed by 12). The count is thus
\underset{n-2}{\underbrace{111\dots1}}.

Tally all these up, we have total count of
1+2\times\underset{n-2}{\underbrace{111\dots1}}+(n-2)\times10^{n-3}.

999

For positions 3 through n, again use digits in other positions to count.

For position 2, the pattern is a little bit different: First, the head (alone with the digits between them) is subtracted by 1; for example, 899 is counted instead of 999, for the combination 899(900). Second, because of this subtract by 1, no overlapping is possible, hence no -1 digits case. Fortunately, this only means there are one less then the count of position 2 of 111. As a comparison, for n=5 and p=2 the numbers counted are 899(900); 8999(9000), 9099(9100), 9199(9200), through 9899(9900); 89999(90000), 90099(90100), 90199(90200), through 99899(99900); a total of 111 numbers.

For position 1, similar subtract by 1 happened, but because there's no -1 digit cases in the beginning, the count of position 1 is the same as those of 111.

So the total count is just one less than the case of 111, ie.
2\times\underset{n-2}{\underbrace{111\dots1}}+(n-2)\times10^{n-3}.

Tally up

The total counts of these cases can be further classified into three groups:

  • (n-2)\times10^{n-3}
    All 10 cases has one of this in the sum.
  • \underset{n-2}{\underbrace{111\dots1}}
    There are two of this each in 111 through 999, and a negative one of this in 000, a total of 17.
  • Others, includes n-2 from 000 and eight 1 from 111 through 888, a total of n+6.

So the grand total is thus
\underset{n-2}{\underbrace{111\dots1}}\times17+10\times(n-2)\times10^{n-3}+n+6\=1\underset{n-3}{\underbrace{888\dots8}}7+(n-2)\times10^{n-2}+n+6\={n-1}\underset{n-2}{\underbrace{888\dots8}}+n+5

The {n-1} in the front means it's not multiplication, but the digits of n-1 is concatenated before these 8s. Let's list first few out:

n output
4 388+4+5=397
5 4888+5+5=4898
6 58888+6+5=58899
7 688888+7+5=688900
8 7888888+8+5=7888901
9 88888888+9+5=88888902

We can easily see the pattern to the output number. This is easy enough for a short program.

For my program, because fifteen 8s is smaller than 2^53, we can convert these 8s to number, adds n+5, then prepend (as string) n-1. For other languages that cannot manipulate digits that easily, the closed form of the answer is
\left\lfloor\frac{(9n-1)\times10^{n-2}}{9}\right\rfloor+n+5
where the bracket is the floor function. This formula, as @Aleksandar_B pointed out, works with n=2 (output 8) and n=3 (output 36); the discussion above is all valid in these cases.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment