Multi Query Fibonacci
Python
Medium
3 views
Problem Description
Read q queries, each query is n. Make a fib function and answer all queries fast using memoization.
Input Format
First line q. Next q lines: n.
Output Format
q lines fib(n).
Official Solution
import sys
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
q=int(lines[0].strip())
mem={0:0,1:1}
def fib(x):
if x in mem:
return mem[x]
a=0
b=1
for i in range(2,x+1):
a,b=b,a+b
mem[x]=b if x>0 else 0
return mem[x]
out=[]
for i in range(q):
n=int((lines[1+i] if 1+i<len(lines) else '0').strip())
out.append(str(fib(n)))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!