loading...

Daily HackerRank Challenge - Day 30

wingkwong profile image Wing-Kam ・2 min read

Daily HackerRank Challenge (30 Part Series)

1) Daily HackerRank Challenge - Day 0 2) Daily HackerRank Challenge - Day 1 3 ... 28 3) Daily HackerRank Challenge - Day 2 4) Daily HackerRank Challenge - Day 3 5) Daily HackerRank Challenge - Day 4 6) Daily HackerRank Challenge - Day 5 7) Daily HackerRank Challenge - Day 6 8) Daily HackerRank Challenge - Day 7 9) Daily HackerRank Challenge - Day 8 10) Daily HackerRank Challenge - Day 9 11) Daily HackerRank Challenge - Day 10 12) Daily HackerRank Challenge - Day 11 13) Daily HackerRank Challenge - Day 12 14) Daily HackerRank Challenge - Day 13 15) Daily HackerRank Challenge - Day 14 16) Daily HackerRank Challenge - Day 15 17) Daily HackerRank Challenge - Day 16 18) Daily HackerRank Challenge - Day 17 19) Daily HackerRank Challenge - Day 19 20) Daily HackerRank Challenge - Day 20 21) Daily HackerRank Challenge - Day 21 22) Daily HackerRank Challenge - Day 22 23) Daily HackerRank Challenge - Day 23 24) Daily HackerRank Challenge - Day 24 25) Daily HackerRank Challenge - Day 25 26) Daily HackerRank Challenge - Day 26 27) Daily HackerRank Challenge - Day 27 28) Daily HackerRank Challenge - Day 28 29) Daily HackerRank Challenge - Day 29 30) Daily HackerRank Challenge - Day 30

About

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


Fibonacci Numbers

image

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]=0;
memo[1]=memo[2]=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]=0;
    memo[1]=memo[2]=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)

1) Daily HackerRank Challenge - Day 0 2) Daily HackerRank Challenge - Day 1 3 ... 28 3) Daily HackerRank Challenge - Day 2 4) Daily HackerRank Challenge - Day 3 5) Daily HackerRank Challenge - Day 4 6) Daily HackerRank Challenge - Day 5 7) Daily HackerRank Challenge - Day 6 8) Daily HackerRank Challenge - Day 7 9) Daily HackerRank Challenge - Day 8 10) Daily HackerRank Challenge - Day 9 11) Daily HackerRank Challenge - Day 10 12) Daily HackerRank Challenge - Day 11 13) Daily HackerRank Challenge - Day 12 14) Daily HackerRank Challenge - Day 13 15) Daily HackerRank Challenge - Day 14 16) Daily HackerRank Challenge - Day 15 17) Daily HackerRank Challenge - Day 16 18) Daily HackerRank Challenge - Day 17 19) Daily HackerRank Challenge - Day 19 20) Daily HackerRank Challenge - Day 20 21) Daily HackerRank Challenge - Day 21 22) Daily HackerRank Challenge - Day 22 23) Daily HackerRank Challenge - Day 23 24) Daily HackerRank Challenge - Day 24 25) Daily HackerRank Challenge - Day 25 26) Daily HackerRank Challenge - Day 26 27) Daily HackerRank Challenge - Day 27 28) Daily HackerRank Challenge - Day 28 29) Daily HackerRank Challenge - Day 29 30) Daily HackerRank Challenge - Day 30

Posted on May 12 by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

markdown guide