Problem: Fibonacci Sum

*Difficulty: Easy

Given a number positive number n, find value of f0 + f1 + f2 + …. + fn where fi indicates i’th Fibonacci number. Remember that f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5, …

Input  : n = 3
Output : 4
Explanation : 0 + 1 + 1 + 2  = 4

Input  :  n = 4
Output :  7
Explanation : 0 + 1 + 1 + 2 + 3  = 7

Since the answer can be very large, answer modulo 1000000007 should be printed.

Input:
First line contains an integer, the number of test cases ‘T’ Each test case should contain a positive integer N.
Output:
Print sum of fibonacci numbers.
Constraints:
1 <=T<= 20000
1 <= N <=100000
Example:
Input:
2
6
5

Output:
20
12

Implementation: Python2.7
Sum of first nth fibo

#code
def sum_first_100k_fibo():
    # this will be faster than
    # calculate and return first-100k-fibo-number list
    f1, f2 = 1, 2
    fibo = [f1, f2]
    yield f1
    yield f2
    while len(fibo) < 100000:
        f1, f2 = f2, f1+f2+1
        fibo.append(f2)
        yield f2

if __name__ == '__main__':
    fibo = sum_first_100k_fibo()
    fibo_dict = []
    for i in range(100000):
        fibo_dict.append(fibo.next())
    t = input()
    for _ in range(t):
        n = input()
        print fibo_dict[n-1] % 1000000007 

Advertisements