23
Introduction
Let's observe the following sequence (non-negative integers):
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
For example, let's take the first three numbers. These are 0, 1, 2
. The numbers used in this sequence can be ordered in six different ways:
012 120
021 201
102 210
So, let's say that F(3) = 6. Another example is F(12). This contains the numbers:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Or the concatenated version:
01234567891011
To find the number of ways to rearrange this, we first need to look at the length of this string. The length of this string is 14
. So we compute 14!. However, for example the ones can exchange places without disrupting the final string. There are 2 zeroes, so there are 2! ways to exhange the zeroes without disrupting the order. There are also 4 ones, so there are 4! ways to switch the ones. We divide the total by these two numbers:
This has 14! / (4! × 2!) = 1816214400 ways to arrange the string 01234567891011
. So we can conclude that F(12) = 1816214400.
The task
Given N, output F(N). For the ones who don't need the introduction. To compute F(N), we first concatenate the first N non-negative integers (e.g. for N = 12, the concatenated string would be 01234567891011
) and calculate the number of ways to arrange this string.
Test cases
Input: Output:
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 119750400
12 1816214400
13 43589145600
14 1111523212800
15 30169915776000
Note
Computing the answer must be computed within a time limit of 10 seconds, brute-forcing is disallowed.
This is code-golf, so the submission with the least amount of bytes wins!
Is the output for
10
correct? It feels like it should be less than 10!, since that's where the repeating digits start. – Geobits – 2016-02-03T22:02:05.707@Geobits The first
10
digits are0, 1, 2, 3, 4, 5, 6, 7, 8, 9
. Ten different digits, so the result is 10!. – Adnan – 2016-02-03T22:03:41.323Ah, right. I think the
0
case was throwing my count off (stupid empty strings). – Geobits – 2016-02-03T22:05:20.987You only need to support the test cases that your language can handle. Natively? This needs one more upvote to count as standard loophole... – Dennis – 2016-02-04T00:37:53.437
@Dennis Hmmm, good point. I have deleted the rule in the post. – Adnan – 2016-02-04T08:05:31.953
1No need to worry about that anymore. The loophole proposal was at +4 when I posted the comment. It is at +9 now. – Dennis – 2016-02-04T16:09:06.470
1Here's an interesting math question about this puzzle: What is the value of F(N) relative to N!? There are a number of values of N for which F(N)/F(N-1) < N, but it is usually slightly greater. I'm pretty sure that
F(N)
is notO(N!)
and thatlog F(N)
isO(log N!)
but those are just hunches... – rici – 2016-02-05T03:10:48.543