Basic / Intermediate / Hard Difficulty :

Python 3 -

I came up with this solution only to find I am late and someone(betamaster97156) had already submitted with nearly same algorithm. Anyway, my approach focus on speed and less on memory management.

https://repl.it/JAOU/8

```
from time import time
def fibonacciFinder(): # return 50th number of fibonacci
a, b = 0, 1
for x in range(48):
a, b = b, a + b
return b
def fibonacciFinderN(N):
# A dictionary to store value of few particular numbers of the fibonacci series
fibDict = {1:0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 5, 7: 8, 8: 13, 9: 21, 10: 34,
11: 55, 12: 89, 13: 144, 14: 233, 15: 377, 16: 610, 17: 987, 18: 1597, 19: 2584, 20: 4181,
21: 6765, 22: 10946, 23: 17711, 24: 28657, 25: 46368, 26: 75025, 27: 121393,
'f25': 46368,'f26': 75025,'f27': 121393,
'f100': 218922995834555169026, 'f101': 354224848179261915075, 'f102': 573147844013817084101,
'f500': 86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501, 'f501': 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125, 'f502': 225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626,
'f5000': 2397334346100631452333336800023778743396400988090212332865227234032387117767626167465060795065595580850691237390963845987165478074085124644348902530685083246709423858342692329718110162972268152200857232686119638781547238020078362945470777668711057069618425746387920931255084621360135655698456629322111614827324455767748623844363426260372374195153577101298837831208580530677289982029527164306876024342838547454228388796380077029917639469963653048076473269452943584037848773158456736367057460079075603072996653089318046279296240100777360367200040226807430924334616931577257195085793060133817911514540227011756335999604550121968663793604830945238116686325506344893928776515696088851468818023735825546502317562957459506612704850760351077006532507519813600498603205937022956740021970327599548184626715032015801445754074519753924901317605013561516613650173445818028242577356369143977719495739428130191089993769093308407443558168431535751910046557480949313497996285124526992631353143367314930548703966553707195171094152730704138121243470432644848607501, 'f5001': 3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125, 'f5002': 6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626}
# return value from index using the dictionary
if N < 25:
return fibDict[N]
N += 1
a, b, count = 0, 1, 1
# Every number in fibonacci is multiple addition of first two number 0 and 1
# Using that reduce the two variables repeatedly
# Formula - f(x+n) = f(x+1)*f(n-1) + f(x+2)*f(n)
# Example - f10 = f9*f1 + f10*f2 = 21*f1 + 34*f2 here => x = 8, n = 2 and f1 = 0, f2 = 1
while N - count > 25:
if N - count > 5000: # x = 5000
count += 5000
a, b = fibDict['f5000'] * a + fibDict['f5001'] * b, fibDict['f5001'] * a + fibDict['f5002'] * b
elif N - count > 500: # x = 500
count += 500
a, b = fibDict['f500'] * a + fibDict['f501'] * b, fibDict['f501'] * a + fibDict['f502'] * b
elif N - count > 100: # x = 100
count += 100
a, b = fibDict['f100'] * a + fibDict['f101'] * b, fibDict['f101'] * a + fibDict['f102'] * b
else: # x = 25
count += 25
a, b = fibDict['f25'] * a + fibDict['f26'] * b, fibDict['f26'] * a + fibDict['f27'] * b
if N - count == 1:
return a
else:
# Using the above formula
return fibDict[N - count - 1] * a + fibDict[N - count] * b
print(f'fibonacciFinder() => {fibonacciFinder()}')
print(f'fibonacciFinderN(300) => {fibonacciFinderN(300)}')
t = 0
for x in range(10000):
start = time()
fibonacciFinderN(x+1)
end = time()
t += end - start
print(f'Time taken to find first 10000 numbers in fibonacci is {t} seconds')
```

I also tried to solve this problem with golden ratio formula, but it was very slow, if I tried to get precise values(even though it’s time complexity is O(1)) compared to this solution.