We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Although it's curious to find a non-iterative, closed-form solution, this isn't a practical method at all. We're doing integer arithmetic with integers of size O(n2) bits, and in fact, before performing the final bit-wise and, we've got an integer that is the first n Fibonacci numbers concatenated together!
To be fair, if this were an actual interview question, I think I would want to point out that the naive recursive solution (without memoization or special formulas) is absolutely the worst way to compute Fibonacci numbers. If you draw out the call tree for say fib(10), you see that the function gets called a crazy number of times with the same values. The iterative version is just a better solution.
How, without memoization or special formulas? To elaborate a bit more, here is a list of the different methods I can think of for computing the Fibonacci numbers:
Binet's formula
Iterative solution without memoization
Iterative solution with memoization
Recursive solution without memoization
Recursive solution with memoization
Recursive solution using formulas for F(2n) and F(2n+1) with or without memoization.
If you only plan to call the function a few times and you're not worried about possible floating point errors, then 1 is the best. If you're calling it many times, then 3 is better than 5 is better than 1. If you need to calculate really large Fibonacci numbers, then 6 is the best. Without memoization the performance of solution 4 is horrible.
#include<iostream>usingnamespacestd;voidfibonacci(intn,int*fn,int*fn1){// Complete the function.if(n==1){*fn=1;*fn1=0;return;}intfn_,fn1_;fibonacci(n-1,&fn_,&fn1_);*fn=fn_+fn1_;*fn1=fn_;}intmain(){intn;intfn,fn1;cin>>n;fibonacci(n,&fn,&fn1);cout<<fn;return0;}
Implementation with cache to reduce redundant calculations and help with response times.
static Map cache = new HashMap();
public static int fibonacci(int n) {
if(n==0) return 0;
if(n==1) return 1;
if(cache.get(n) != null) return (int) cache.get(n);
int a = fibonacci(n-1);
int b = fibonacci(n-2);
cache.put(n-1,a);
return a+b;
}
Here was my idea which is similar, but easier to read/remember because it's more mechanical--the modulo math is removed, and instead an extra copy operation is used to keep the array ordered newest-to-oldest. Special case 0 and start the loop at 1.
Recursion: Fibonacci Numbers
You are viewing a single comment's thread. Return to all comments →
O(n) time-complexity; O(1) space-complexity. Passes all cases.
Nice :)
Here is a one-liner in python,
Complexity :
Oh wow! How does this work?
TBH, I took it from here. It evaluates a closed-form expression. You can learn about it here too. :)
here is problem solution in java python c++ c and javascript programming.
HackerRank Recursion: Fibonacci Numbers solution
Python one-liners are so sexy.
C++ one-liners are sexy, too (and rare?):
Unfortunately most oneliners suffer from unreadability.
Time Complexity is high. O(2^n)
please explain this problem
holly shit.... lambda as supre powerful...
Not sure you'd want to use it, though.
Well done.
Recursive method, one-liner Python, passed all test cases
To be picky: The problem asked for recursion :P
Yep, I agree on that. Just sharing different solutions :)
To be fair, if this were an actual interview question, I think I would want to point out that the naive recursive solution (without memoization or special formulas) is absolutely the worst way to compute Fibonacci numbers. If you draw out the call tree for say fib(10), you see that the function gets called a crazy number of times with the same values. The iterative version is just a better solution.
but you can do it recursively in O(n) time complexity with O(n) space complexity
How, without memoization or special formulas? To elaborate a bit more, here is a list of the different methods I can think of for computing the Fibonacci numbers:
If you only plan to call the function a few times and you're not worried about possible floating point errors, then 1 is the best. If you're calling it many times, then 3 is better than 5 is better than 1. If you need to calculate really large Fibonacci numbers, then 6 is the best. Without memoization the performance of solution 4 is horrible.
I was referring to 5. Recursive solution with memoization
Cool trick!
Implementation with cache to reduce redundant calculations and help with response times.
static Map cache = new HashMap();
public static int fibonacci(int n) { if(n==0) return 0; if(n==1) return 1; if(cache.get(n) != null) return (int) cache.get(n); int a = fibonacci(n-1); int b = fibonacci(n-2); cache.put(n-1,a); return a+b; }
Here was my idea which is similar, but easier to read/remember because it's more mechanical--the modulo math is removed, and instead an extra copy operation is used to keep the array ordered newest-to-oldest. Special case 0 and start the loop at 1.
I am not able to get this.... n%2 is either equal to 1 or 0. which means that the function will return value either 1 or 0 for any fibonacci n.
This is cool.
without a loop in C#, so O(1) time and complexity https://math.stackexchange.com/questions/90821/how-to-find-the-closed-form-to-the-fibonacci-numbers
Reread the specifications. You have to solve it recursively calling fibonacci.