# FIBONACCI - Editorial

Practice
Contest
Author: Pratik
Tester: Varun
Editorialist: Pratik

MEDIUM .

Greedy, STL.

# PROBLEM:

### Normal form of Fibonacci series upto N is A1, A2, A3, …, AN-1, AN.

Our special fibonacci series is A1, AN, A2, AN-1, …, AN/2.
For a given N, print the first M numbers for this special Fibonacci series.
As the numbers can be very big, print the number modulo 1000000007.

# EXPLANATION:

• For N=10 Fibonacci series would be: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

• And is the above order it would be: [0, 34, 1, 21, 1, 13, 2, 8, 3, 5]

• To print first M numbers: 0 34 1 21 1 13

Basically, we will take normal fibonacci series as input , then we will check index of i if i is odd we will print odd index from normal fibonacci series, otherwise we will print even index of fibonacci series.

# SOLUTION:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;
int modd=1000000007;
long long int fibarr[1000001];
void fibb(void)
{
fibarr[0]=0;
fibarr[1]=1;
for(int i=2;i<=1000001;i++)
{
fibarr[i] = (fibarr[i-1]+fibarr[i-2])%modd;
}
}

int main()
{
int t;
cin>>t;
fibb();
while(t–)
{
int n,m;
cin>>n>>m;
int odd=0;
int even=n-1;
vectorres;
for(int i=0;i<=m;i++)
{

if(i%2==1)
{
res.push_back(fibarr[even]);
even–;
}
else
{
res.push_back(fibarr[odd]);
odd++;
}

}
for(int i=0;i<m;i++)
{
cout<<res[i]<<" ";
}
cout<<endl;
}
}

Tester's Solution

import sys
fib=[0](106 + 1)
fib[1]=1
mo=109+7
for i in range(2,10
6+1):
fib[i]=(fib[i-1]+fib[i-2])
for _ in range(int(input())):
n,m=map(int,input().split())
left=0;right=n-1
for i in range(m):
if(i%2):
print(fib[right],end=" “)
right-=1
else:
print(fib[left],end=” ")
left+=1

Editorialist's Solution

import java.io.*;
import java.util.Arrays;

class Main
{
public static void main(String[] args) throws Exception{
Solution obj = new Solution();
while(T–>0){
}

}
}

class Solution {
int nums[] = new int[1000000];
int M = 1000000007;
Solution(){
nums[0] = 0; nums[1] = 1;
for(int i=1; i<1000000-1;i++){
nums[i+1] = (nums[i]+nums[i-1])%M;
}
}
String solve(String[] arr){
int n = Integer.parseInt(arr[0]), m = Integer.parseInt(arr[1]);
int i;

StringBuilder s = new StringBuilder();
int rev = 0, front = 0;
for(i = 0 ; i<m;i++){
if ((i%2)==0){
s.append(nums[front]);
front++;
} else {
s.append(nums[n - rev-1]);
rev++;
}
s.append(" ");
}

return s.toString().trim();

}

}