where am i going wrong?
arr =[0,1]
for x in range(60-2):
arr.append((arr[-1]+arr[-2])%10)
def red(arr,n):
brr = arr[:n]
while(len(brr)!=1):
brr = brr[1::2]
return brr[0]
tc = int(input())
for i in range(tc):
num = int(input())
print(red(arr,num%60))
plss tell me where its exceeding time limit
Can someone point out the error in my code?
import java.util.*;
class Fibnocci {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int t,n,ans;
ArrayList<Integer>a = new ArrayList<Integer>();
ArrayList<Integer>e = new ArrayList<Integer>();
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
while(t>0){
n = sc.nextInt();
a.add(0);
a.add(1);
for(int i=2;i<n;i++){
a.add(a.get(i-1)+a.get(i-2));
}
for(int i=0;i<n;i++){
a.set(i, a.get(i)%10);
}
if(a.get(a.size()-1)==1){
while(a.size()>1){
for(int i=0;i<a.size();i++){
if(i%2==0){
a.set(i,-1);
}
}
for(int i=0;i<a.size();i++){
if(a.get(i)==-1){
a.remove(i);
}
}
}
}
ans=a.get(0);
System.out.println(ans);
t--;
}
}
}For people who need more clear explanation of the editorial can go to the GitHub link: Easy Fibonacci
can anyone check why i am getting wrong answer on this::
double n = in.readDouble();
int x = (int)(Math.log(n) /
Math.log(2));
x = (int)Math.pow(2, x);
out.printLine(fib(x-1)%10);
out.flush();
//fib(x-1) is implemented in logn using matrix expo
@as_max_rider You can check your program output for the following test-cases:
4
9
72057594037927935
72057594037927936
18014398509481983
Output shoud be:
3
3
0
9
If your program is not giving the correct answer then read the editorial: Easy Fibonacci
Probably there is problem with how you are calculating log. Does your log function gives correct answers for large values.
NOTE: You don’t need to use matrix exponentiation.
You can also read the following post: FIBEASY Matrix Exponentiation Solution? O(lgn) (edit: this solution failed for subcase 3 Yet I am producing right answers?) - #3 by striker22
you were right!!
my problem was with the log function.
my idea was almost same as the editorial except i didn’t use the periodicity part…
i observed a relation among the numbers
1 Like
hey everyone. cant i avoid TLE using this method i have done?
Hi,
I am seriously facing trouble understanding that. Can anybody give me an easy explanation.
Or handily you can avoid any sort of log function - use the bit_length() function of int class.
1 Like
my code nXxuep - Online C++ Compiler & Debugging Tool - Ideone.com
is partially correct, is it wrong to use log2(n) for large inputs…?
Thanks in advance…!
This solution seems to give 0 for the testcase:
1
84
In general, it’s a bad idea to use floating point where an integer solution is expected (though it’s OK sometimes e.g. sqrt when testing for primality, etc). People have come up with testcases where the use of log gives the wrong answer for FIBEASY - see e.g. here and the post linked from that post.
1 Like
Why website shows runtime error of problem code fibeasy?
#include<stdio.h>
int main(){
int T, N, j;
int f[50];
int first = 0,second = 1;
f[0] = first;
f[1] = second;
scanf("%d",&T);
while(T–){
scanf("%d",&N);
for(int i=2;i<N;i++){
f[i] = first + second;
first = second;
second = f[i];
}
}
for(int i=0;i<N;i++)
f[i] = f[i]%10;
while(N){
j=0;
for(int i=1;i<N;i=i+2){
f[j] = f[i];
j++;
}
N = N/2;
}
printf("%d",f[N]);
}
https://www.codechef.com/viewsolution/31854386
Can anybody review this solution of mine and tell me why is it showing TLE and how can i make it more efficient?
can anyone tell why my code (SEE THIS) is giving partially correct for subtask1 and wrong answer for subtask2
So we should basically know that fibonacci no.s mod 10 are periodic with period 60. So vague, isn’t it?
Or do they expect us to figure it out?
This 
1 Like
Well I read about Pisano period, its written that its not possible to manually calculate it for a given integer. (here)
Should we print the values and check ? Sounds very tedious and counterintuitive.
I can’t remember what I did - I either printed out the values, spotted the pattern and deduced why; or the other way around 
The logic behind it is fairly simple:
1 Like