22
2
You should write a program or function which given three positive integers n b k
as input outputs or returns the last k
digits before the trailing zeros in the base b
representation of n!
.
Example
n=7 b=5 k=4
factorial(n) is 5040
5040 is 130130 in base 5
the last 4 digits of 130130 before the trailing zeros are 3013
the output is 3013
Input
- 3 positive integers
n b k
where2 <= b <= 10
. - The order of the input integers can be chosen arbitrarily.
Output
- A list of digits returned or outputted as an integer or integer list.
- Leading zeros are optional.
- Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).
Examples
New tests added to check correctness of submissions. (They are not part of the under 1 minute runtime rule.)
Input => Output (with the choice of omitting leading zeros)
3 10 1 => 6
7 5 4 => 3013
3 2 3 => 11
6 2 10 => 101101
9 9 6 => 6127
7 10 4 => 504
758 9 19 => 6645002302217537863
158596 8 20 => 37212476700442254614
359221 2 40 => 1101111111001100010101100000110001110001
New tests:
----------
9 6 3 => 144
10 6 3 => 544
This is code-golf, so the shortest entry wins.
1under a minute on my computer is a little difficult to aim for if we don't know any specifics. – Dennis – 2015-04-30T17:04:18.137
1Would
7 5 3
output "013" or "13"? – Claudiu – 2015-04-30T17:06:43.0901@Claudiu based on the
7 10 4
test case I would say13
– Maltysen – 2015-04-30T17:07:33.0702@Claudiu "Leading zeros are optional." so both version is correct. – randomra – 2015-04-30T17:12:45.177
I'm having a hard time understanding the algorithm necessary. Can someone help explain? I'm looking here, but it's a bit different since there's a change of base: http://mathforum.org/library/drmath/view/71768.html
– mbomb007 – 2015-04-30T17:13:23.007If we choose integer list for output, does endianness matter? – Dennis – 2015-04-30T17:16:39.537
@Dennis Yes, endianness matters. I used the 1 min rule to clearly separate the simple O(n^2) algorithms from the rest but that might have been a failed attempt. – randomra – 2015-04-30T17:24:39.757
wont you settle a score-meter for this ? – Abr001am – 2015-04-30T22:41:49.150
Is a list of integers as output OK, or is a string required? – isaacg – 2015-05-01T02:09:18.147
@isaacg It is ok. "A list of digits returned or outputted as an integer or integer list." (just edited the
,
toor
). – randomra – 2015-05-01T02:13:54.593Do you have bounds for n? – Brian J – 2015-05-01T17:19:04.623
1Must we accept any positive integer for
n
ork
? Or can we limit them to the range of the language's integer type? – Toby Speight – 2016-01-19T21:06:37.917@TobySpeight Your integer type can limit the range where you can solve the problem but the given should cause no problem for your code. – randomra – 2016-01-19T22:12:02.763
Are you going to change the accepted answer with the renewed interest? – Adám – 2016-01-20T22:09:42.080