Same problem with memorization, and from the conversation above, using this technique appears to be unnecessary. I really wonder where my code went wrong…
@genevieve First of all, maybe use double instead of float (if suitable for your language).
And here are two additional large testcases.
In & out #1
100
8122.68 5968.7 4355.61 7400.36 7593.83 6074.49 3540.57 5393.62 2524.41 9931.84 1601.6 2550.51 5902.75 3071.5 8887.5 7099.46 6621.4 987.0 6325.89 6544.35 4350.52 9338.62 9490.75 2080.04 5407.29 36.39 6853.86 4652.31 3616.58 5293.64 3147.07 8479.25 2121.97 2826.89 8719.37 2659.51 1049.72 9151.21 7429.96 9116.9 2101.6 5787.92 2456.24 998.31 5216.65 1375.89 5159.8 7035.88 6205.43 3312.09 3467.25 4907.05 8691.9 1810.88 3134.07 5329.08 3641.14 2556.6 5399.21 6702.21 4347.61 5749.29 9801.56 7407.04 4188.2 7231.44 8143.99 5528.51 2561.13 9872.88 5042.45 2752.91 9973.54 5002.94 9519.15 9167.88 7165.24 7155.68 8144.04 8967.01 7950.36 9028.19 2384.8 5237.78 9917.35 6182.44 6803.11 5942.19 1132.47 7065.26 6235.37 8436.52 6997.29 5229.42 3451.42 8240.66 2602.82 1183.94 5811.96 3156.37
22074 16219 11835 20111 20637 16507 9619 14656 6857 26992 4349 6928 16040 8344 24153 19293 17994 2679 17190 17784 11821 25380 25793 5649 14693 96 18625 12641 9826 14384 8550 23044 5763 7679 23696 7224 2849 24870 20191 24777 5708 15728 6672 2709 14175 3736 14021 19120 16863 8998 9420 13334 23622 4918 8514 14481 9893 6945 14671 18213 11813 15623 26638 20129 11380 19652 22132 15023 6957 26832 13702 7478 27105 13594 25870 24915 19472 19446 22132 24369 21606 24536 6478 14233 26953 16800 18487 16147 3074 19200 16944 22927 19015 14210 9377 22395 7070 3214 15793 8575
In & out #2
100
5947.46 5906.51 1470.03 8491.62 5326.44 4451.1 6141.63 3260.04 2679.24 3926.19 1451.93 4917.84 4681.44 2149.61 4962.22 6378.59 333.15 4576.89 3256.08 6237.72 3526.56 9029.72 2029.51 788.31 7675.5 9047.6 162.28 5384.58 1713.71 8294.47 5873.84 2183.99 1693.3 5969.21 3024.25 5513.74 5879.69 246.49 4230.22 7750.69 8544.25 1228.9 4200.01 4375.64 5977.09 4673.92 49.69 977.19 9115.06 965.1 259.05 1280.53 9551.66 591.08 6285.82 9545.07 6651.84 9712.45 2653.65 388.8 5097.69 8739.92 6462.66 3032.5 7194.34 1763.95 8543.8 1570.08 5655.96 6649.71 2917.88 7342.18 9839.85 8165.46 9833.92 8060.26 7886.58 9541.3 6667.72 4122.08 219.0 5527.31 2798.11 5841.33 5702.08 866.55 9097.08 1688.98 8835.82 2584.83 4266.65 2979.3 2830.02 412.17 9975.78 8569.76 6607.31 8924.12 1501.71 9468.03
16162 16050 3991 23077 14474 12094 16689 8857 7278 10667 3942 13363 12720 5838 13484 17334 902 12436 8846 16951 9581 24540 5512 2139 20859 24588 438 14632 4654 22541 15961 5932 4598 16221 8216 14983 15977 666 11494 21063 23220 3336 11412 11889 16242 12700 132 2652 24772 2619 700 3476 25959 1603 17081 25941 18076 26396 7209 1053 13852 23752 17562 8238 19551 4790 23219 4263 15369 18070 7927 19953 26742 22191 26726 21905 21433 25930 18119 11200 592 15020 7601 15873 15495 2351 24723 4586 24013 7021 11593 8094 7688 1116 27111 23290 17955 24253 4077 25731
I was already using “long double” in C++…
Thanks for the extra test cases! 
Actually, @Niako, the first part of your comment was more relevant than I first thought! I was thinking in C like in https://stackoverflow.com/questions/13425012/c-programming-does-float-always-auto-convert-to-double-when-multiplying-mixed-d and I was using float A[] and long double N[]. It looks like float*(long double) = float in C++… !!
Thanks so much, y’all, for your tips 
@genevieve I think your problem must have another explanation because, as detailed here, the float should (as expected) be converted to long double in that case.
true 
There is a nice bit of optimization you can do on top of the solution. This solves the 4th and 5th case under a sec for me.
In Swift, it’s definitely hard due to type-safe,… I’m officially the world first in Swift on this puzzle. The difficulty of this puzzle should be Hard, not Medium.
For A = 10 the result should be 25 according to the 2nd Test Case.
This is my debug output:
N: 0 Pow: 1 Fac: 1
N: 1 Pow: 10 Fac: 1
N: 2 Pow: 100 Fac: 2
N: 3 Pow: 1000 Fac: 6
N: 4 Pow: 10000 Fac: 24
N: 5 Pow: 100000 Fac: 120
N: 6 Pow: 1000000 Fac: 720
N: 7 Pow: 10000000 Fac: 5040
N: 8 Pow: 100000000 Fac: 40320
N: 9 Pow: 1000000000 Fac: 362880
N: 10 Pow: 10000000000 Fac: 3628800
N: 11 Pow: 100000000000 Fac: 39916800
N: 12 Pow: 1000000000000 Fac: 479001600
N: 13 Pow: 10000000000000 Fac: 6227020800
N: 14 Pow: 100000000000000 Fac: 87178291200
N: 15 Pow: 1000000000000000 Fac: 1307674368000
N: 16 Pow: 10000000000000000 Fac: 20922789888000
N: 17 Pow: 1E+17 Fac: 355687428096000
N: 18 Pow: 1E+18 Fac: 6402373705728000
N: 19 Pow: 1E+19 Fac: 1.21645100408832E+17
N: 20 Pow: 1E+20 Fac: 2.43290200817664E+18
N: 21 Pow: 1E+21 Fac: 1.4197454024290337E+19
N: 22 Pow: 1E+22 Fac: 1.7196083355034583E+19
N: 23 Pow: 1.0000000000000001E+23 Fac: 8.128291617894826E+18
N: 24 Pow: 1E+24 Fac: 1.0611558092380307E+19
N: 25 Pow: 1E+25 Fac: 7.034535277573964E+18
1E+25 > 7.034535277573964E+18
Why?
Oh… i see…overflow. Already using ulong 
a^n < n!
Think of an equation. What to you have to do to get the numbers on both sides lower?
A division? But divide what? I mean…to find out what n!/10 is, i have to calculate n! first or not? I really struggle with that task
You are on the right track.
But maybe you never calculate and compare the final results of a^n and n! but divide earlier (on the road there).
If a^n < n! is true, then not only (a^n)/2 < (n!)/2 is always true but also (a^(n-1))/2 * a < ((n-1)!)/2 * n is always true.
And my last tipp: the divisor has not always to be 2.
1 Like
Not necessary division… You may use other mathematical functions to reduce both sides of the inequality to smaller numbers.
1 Like