[Solved] Time limit exceeded – Fibonacci

Optimization comes usually comes in steps.

You start off with the obvious solution.

iterate_fibs_mod10; remove_odds(n);

Then you realize that you really only need the expensive modulus once for one element.

nth_fib(remove_odds(n))%10;

Then you realize you don’t need to remove the nodes if you can deterministically find which one would have remained.

nth_fib(as_if_remove_odds(n))%10;

Then you figure out that the element corresponds to a mathematical function.

nth_fib((int)log2(n))%10;

Then you realize that this corresponds to the most significant bit in binary representation.

nth_fib(msb_only(n))%10; //compiler builtins exist for most significant bit

Then you notice that since you are only doing the last digit, the sequence must repeat within 100 iterations (it happens to be 60), so you can do a lookup table.

unsigned char fib_1s[60] = {...};
fib_1s[msb_only(n)%60];