# Daily HackerRank Challenge - Day 30

Daily HackerRank Challenge (30 Part Series)

This is a series of Daily HackerRank Challenge. Each day I show the some solutions written in C++.

# Fibonacci Numbers Sample Input

3


Sample Output

2


This is a classical question. We can obverse that fibonacci(0) is 0, fibonacci(1) is 1, fibonacci(2) is 1, and starting from n=3, fibonacci(n)=fibonacci(n-1)+fibonacci(n-2). It goes like 0,1,1,2,3,5,8 and so on.

int fibonacci(int n) {
if(n==0) return 0;
if(n==1||n==2) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}


However, if we use this approach, there will be lots of repeating process. For example, fibonacci(4)=fibonacci(3)+fibonacci(2) and fibonacci(3)=fibonacci(2)+fibonacci(1). We can see that fibonacci(2) is duplicate as well as it branches such as fibonacci(1) and fibonacci(0) in this case. Therefore, we can implement Memoization here.

Memoization is an optimization technique to speed up by storing the results of function calls. If we need to call the function, and the function has been called before, we can simply just take the result.

To do that, we can initialise a vector with a value of 0.

vector<int> memo(n+1,0);


Then we know that our first three fibonacci numbers are 0, 1 and 1. We can set them first.

memo=0;
memo=memo=1;


If fibonacci(n) has been calculated, we can return the result immediately. If not, calculate it and return memo[n] afterwards.

if(memo[n]) return memo[n];
memo[n] = f(n-1,memo)+f(n-2,memo);
return memo[n];


Final Solution

int f(int n, vector<int>& memo){
if(memo[n]) return memo[n];
memo[n] = f(n-1,memo)+f(n-2,memo);
return memo[n];
}

int fibonacci(int n) {
vector<int> memo(n+1,0);
memo=0;
memo=memo=1;
return f(n, memo);
}



## Challenge yourself

The above solution can be further optimised. The hint is that we don't actually need memo[n] to store our results. Let's share your thoughts!

# Complete Code

Check out the complete code via below link

# Closing

I think this is the end of this series. After practicing coding in HackerRank for a while, I found that some questions are hard to understand while the description can be simplified. This has been raised out by other users years ago but it is still the same. Besides, some test cases are violated constraints so that you never get it right.

This series being ended doesn't mean I stop practicing coding. I decided to move on to other sites such as LeetCode, AtCoder, and Codeforces. I've created a new series to explain my solutions from these sites. Follow me for timely updates!

Daily HackerRank Challenge (30 Part Series)

### Discussion   