# [Community puzzle] Factorial vs Exponential

#6

I’m using C++. I’ve made my variables long double. But the exponential goes infinite before the factorial catches up on test cases 4 and 5. Is there something bigger than long double? Is there some trick to figure this out that doesn’t involve calculating and comparing A^N and N!? I’m stuck. Thanks for any help you can give me.

#7

MarkWyz, think about mathematical functions that make big numbers smaller…

#8

Thanks for the hint. I finally got it to work 100%.

#10

Can someone help me, I’m stuck on test case 5.
Here’s my c# code:
https://pastebin.com/kZQhrd7J

#11

Increase kmax maybe ? Try 30000

#12

Has anyone solved this for with Python for Test Case #5 Huge Float Values? I’ve get about halfway done in 6 seconds and then get the error.

Process has timed out. This may mean that your solution is not optimized enough to handle some cases.

I’m using a binary search and setting the lower & upper limits based upon previous results each time. Test Case #4 Bigger Float Values completes in under 2 seconds. Wondering if I need to use the gmpy module to complete this…

#13

No, no need. See selenae answer 5 posts above.

#14

Thanks and wow not what I expected.

I had cached the factorials as I calculated them (as the min/max could re-use them for different numbers) but that wasn’t the problem. (Thought for sure that was the long operation and I don’t think that simplifies at all).

Had to take the Log of both sides and then use N*math.log(a) instead of aN in my comparison. This completed within the time limit where as aN would not.

I don’t remember my calculus that well, but I guess the libraries use a Taylor Series to calculate the Log function. Where as the ** operation is performed recursively when an integer is used? Seems odd as I’d expect that operation to convert/simply with natural log functions which could use Taylor Series.

Doesn’t make sense, so maybe I don’t quiet understand it, but problem solved & solution passed!

Thanks Kirbiby & selenae

#15

Again a mathematical puzzle…

two choices : you know the right theorem and you can solve the puzzle easily or you don’t know and you just go to an other puzzle.

#16

Fixed.

#17

You are absolutely right @nicola1.
Thanks,
and found an amazing way to solve the problem.
That, made the problem extremely simple!

Cheers!

#18

Great choice!
That helps

#19

Hi !

I haven’t hardcoded any part of my solution and I can run my code on larger test cases, but I keep failing the last validation. Not in the test cases, but in the evaluation only. I don’t suppose there is any way of knowing what went wrong?

Thanks for any idea,

Genevieve

#20

#21

Hmm, interesting. Indeed, I would not have seen that the error message was different… I’ll try reprogramming with memorization, and see if it helps. Thanks!

#22

Same problem with memorization, and from the conversation above, using this technique appears to be unnecessary. I really wonder where my code went wrong…

#23

@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
``````

#24

I was already using “long double” in C++…

Thanks for the extra test cases!

#25

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

#26

@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.