Hi everyone.
Let's do this question in the Fibonacci sequence.
Each subsequent term is obtained by adding the preceding two terms.
This is true for all the numbers except the first two numbers of the Fibonacci series, as they do not
have two preceding numbers.
The first two terms in the Fibonacci series is zero and one, so we have zero and one, and f of n is
equal to f of n minus one plus f of n minus two for n greater than one.
So when n is greater than one, like for example, when n is equal to two, f of two will be equal to.
F of n minus one, which is f of one plus f of n minus two, which is equal to f of zero.
And these two terms we already know are zero and one.
So when n is equal to two, f of two will be zero plus one, which is equal to one and f of three.
Let's write that also as per this definition over here will be equal to f of three minus one, which
is f of two plus f of three minus two, which is f of one.
So f of two we found is one and f of one is one.
So we need to add these two to get f of three which is equal to one plus one which is two.
All right.
So that's what's given over here.
And this is true for n greater than one.
Write a function.
So this is what we need to do.
Write a function that finds f of n given n where n is an integer greater than equal to zero.
For the first term, n is equal to zero.
All right.
So it's mentioned that the first term.
Is F of zero.
So this is the first term and we will be given n right.
We will be given n.
So basically we just need to write a function where n is given.
And we need to find f of n.
So that's what's given over here.
Right.
A function that finds f of n given n where n is an integer greater than equal to zero.
So n will be zero or 1 or 2, etc..
Right?
So when n is given we have to find f of n.
So this is the question now in the interview.
If you do have any questions about this question you have to ask clarifying questions.
Now over here I'm just proceeding because this is a classic question.
Right.
So you may have already encountered this question.
And we will solve this problem in multiple ways.
And we will try to learn different concepts by solving this question.
Now let's proceed.
So we have established that what we need to write is a function where n is given.
And we need to find f of n.
And it's given that when n is equal to zero, then the value is zero.
When n is equal to one, the value is one, and then this is the value when n is equal to two, and
this is the value when n is equal to three and it goes on like that.
All right.
So let's proceed.
To start with, let's just write out the Fibonacci series to get a good understanding of the Fibonacci
series.
And this is a very famous series, and Fibonacci is the mathematician who introduced this.
All right.
So it's given that the first two terms are zero and one.
And we get the next term by adding up these two terms.
So zero plus one that gives us one which is the next term.
And to get the next term we have to add these two terms.
So one plus one which is equal to two.
So that's the next term.
Again we have to add one and two to get three.
So that's the next term.
And then we add two and three right two and three to get five.
And it goes on like this.
Right.
So three plus five is eight.
And then we get eight plus five is 13.
Eight plus 13 is 21.
And it goes on like that.
So that's the Fibonacci series and it goes on till infinity.
Now over here we are asked to write a function where n is given.
And we have to find f of n.
Now it's also given that when n is equal to zero, we take f of zero which is zero.
So this is f of zero.
All right.
And it's, uh, what else is given?
Let's just write the in.
Right.
Let me just make some space over here so that we can understand what the output should be.
So let me just write n over here.
Now, when n is equal to zero, f of n is zero.
When n is equal to four.
For example, f of four is equal to three, right and f of eight would be 21.
So when f when n is equal to one, f of one is nothing but one.
Right.
Which is this value over here.
Similarly, when n is equal to eight.
F of eight will be equal to 21.
So this is the function that we need to write.
So we've got a good idea about the Fibonacci series and the function that we need to write.
We are given n and we need to find f of n.
And remember f of zero is zero.
This is f of zero.
This is f of one, this is f of eight, etc..
Now let's go ahead.
And in the next section let's discuss how we can solve this.
And we will discuss multiple ways of solving this problem.
And we will discuss the time and space complexity of different ways of solving this question.