## 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

```

## Problem: 1[0]1 Pattern Count

*Difficulty: Eazy

Given a string, your task is to find the number of patterns of form 1[0]1 where [0] represents any number of zeroes (minimum requirement is one 0) there should not be any other character except 0 in the [0] sequence.

Input:
The first line contains T denoting the number of testcases. Then follows description of testcases. Each case contains a string.
Output:
For each test case, output the number of patterns.

Constraints:
1<=T<=20
1<=Length of String<=2000
Example:
Input:
2
100001abc101
1001ab010abc01001

Output:
2
2

Implementation: Python2.7

```def pattern_count(string):
flag_index = string.find('1') # get the first '1' in string
count = 0 # count number of patterns
zero_between = 0 # count number of zero between two 1
i = flag_index # start at first '1' in string
while i < len(string) and i != -1:
if string[i] == '0':
zero_between += 1
elif string[i] == '1':
if zero_between > 0:
count += 1
zero_between = 0
flag_index = i
else:
zero_between = 0
flag_index = string.find('1', flag_index+1)
i = flag_index
i += 0 if i == -1 else 1
print count

if __name__ == '__main__':
t = input()
for _ in range(t):
string = raw_input().strip()
pattern_count(string)

```

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r