C, 150 140 135 bytes
r,d;f(k,x){r=x<5?3:f(k+1,x/5);return(d=x%5)?r*"33436"[d]*(1<<d*k%4)%5:r;}main(int c,char**v){c=atoi(*++v);printf("%d",c<2?1:2*f(0,c));}
This is the version for ASCII systems; replace the string 33436
with 11214
for an EBCDIC system, or with \1\1\2\1\4
for a portable program.
C solutions are a bit hampered by the requirement to provide a full program; however, this does answer the question fully.
Try it online (requires Javascript):
Explanation
It's based on the algorithm outlined in Least Significant Non-Zero Digit of n!, turned around so that we recurse in to find the highest power of five, and do the calculation on the way out. The tables of constants were too big, so I reduced them by finding a relationship between the previous residue r
, the current digit d
and the recursion depth k
:
0 1 2 3 4 =d
0 0 3×2^k 1×2^2k 3×2^3k 2
1 1 1×2^k 2×2^2k 1×2^3k 4
r 2 2 2×2^k 4×2^2k 2×2^3k 3
3 3 3×2^k 3×2^2k 3×2^3k 2
4 4 4×2^k 4×2^2k 4×2^3k 1
For r>0
, this resolves to a constant times r
times 2^dk
(mod 5); the constants are in a[]
below (inlined in the golfed code). We also observe that (2^4)%5
is 1, so we can reduce the exponent to avoid overflowing the range of int
.
const int a[] = { 1, 1, 2, 1, 4 };
int f(int k, int x){
int r = x<5 ? 3 : f(k+1,x/5); /* residue - from recursing to higher-order quinary digits */
int d = x%5;
if (!d)
return r;
return r * a[d] * (1<<d*k%4) % 5;
}
int main(int c, char **v)
{
c = atoi(*++v);
printf("%d",
c<2
? 1 /* special-case 0 & 1 */
: 2*f(0,c)); /* otherwise, it's 2 times r */
}
Tests:
$ for i in 100 1000 10000 100000; do echo $i: `./694 $i`; done
100: 4
1000: 2
10000: 8
100000: 6
1000000: 4
Performance is respectable, too. Here's a maximum input for a system with 32-bit int
:
$ time ./694 2147483647
8
real 0m0.001s
user 0m0.000s
sys 0m0.000s
I got the same timings with a maximal 64-bit int
, too.
Single function or complete program? – Joey – 2011-02-08T12:15:39.020
@joey No, they are just test cases. Single Input, Single Output. – fR0DDY – 2011-02-08T14:09:50.733
@joey Complete program. – fR0DDY – 2011-02-08T14:36:10.163
Why not 0! as well? – Jo King – 2018-01-18T07:00:04.057
1Requirement for a full program is discouraged... – Erik the Outgolfer – 2018-01-18T16:12:08.977
2@EriktheOutgolfer this is from ~7 years ago, so I don't think that was determined at the time – NoOneIsHere – 2018-01-18T22:35:13.890
@NoOneIsHere Well it is now, but I still believe that, even back then, people would have preferred to be able to write either a full program or a function, instead of being restricted to a full program. – Erik the Outgolfer – 2018-01-19T11:16:28.820
is extra output okay? such as [2,1] for 5? or 2\n1 – FantaC – 2018-02-13T16:14:47.137