1
00:00:01,040 --> 00:00:01,940
Hi everyone.

2
00:00:01,940 --> 00:00:05,900
Let's do this question in the Fibonacci sequence.

3
00:00:05,900 --> 00:00:10,850
Each subsequent term is obtained by adding the preceding two terms.

4
00:00:10,850 --> 00:00:16,970
This is true for all the numbers except the first two numbers of the Fibonacci series, as they do not

5
00:00:16,970 --> 00:00:18,560
have two preceding numbers.

6
00:00:18,560 --> 00:00:25,160
The first two terms in the Fibonacci series is zero and one, so we have zero and one, and f of n is

7
00:00:25,160 --> 00:00:30,560
equal to f of n minus one plus f of n minus two for n greater than one.

8
00:00:30,560 --> 00:00:37,010
So when n is greater than one, like for example, when n is equal to two, f of two will be equal to.

9
00:00:37,890 --> 00:00:44,460
F of n minus one, which is f of one plus f of n minus two, which is equal to f of zero.

10
00:00:44,460 --> 00:00:47,460
And these two terms we already know are zero and one.

11
00:00:47,460 --> 00:00:53,250
So when n is equal to two, f of two will be zero plus one, which is equal to one and f of three.

12
00:00:53,250 --> 00:00:58,920
Let's write that also as per this definition over here will be equal to f of three minus one, which

13
00:00:58,920 --> 00:01:03,780
is f of two plus f of three minus two, which is f of one.

14
00:01:03,780 --> 00:01:07,230
So f of two we found is one and f of one is one.

15
00:01:07,230 --> 00:01:12,300
So we need to add these two to get f of three which is equal to one plus one which is two.

16
00:01:12,300 --> 00:01:12,720
All right.

17
00:01:12,720 --> 00:01:13,950
So that's what's given over here.

18
00:01:13,950 --> 00:01:16,020
And this is true for n greater than one.

19
00:01:16,020 --> 00:01:17,280
Write a function.

20
00:01:17,280 --> 00:01:18,870
So this is what we need to do.

21
00:01:18,870 --> 00:01:26,430
Write a function that finds f of n given n where n is an integer greater than equal to zero.

22
00:01:26,430 --> 00:01:29,040
For the first term, n is equal to zero.

23
00:01:29,040 --> 00:01:29,640
All right.

24
00:01:29,640 --> 00:01:33,240
So it's mentioned that the first term.

25
00:01:34,540 --> 00:01:36,220
Is F of zero.

26
00:01:36,430 --> 00:01:40,840
So this is the first term and we will be given n right.

27
00:01:40,840 --> 00:01:42,070
We will be given n.

28
00:01:42,070 --> 00:01:45,670
So basically we just need to write a function where n is given.

29
00:01:45,670 --> 00:01:47,380
And we need to find f of n.

30
00:01:47,380 --> 00:01:48,850
So that's what's given over here.

31
00:01:48,850 --> 00:01:49,300
Right.

32
00:01:49,300 --> 00:01:55,240
A function that finds f of n given n where n is an integer greater than equal to zero.

33
00:01:55,240 --> 00:01:58,210
So n will be zero or 1 or 2, etc..

34
00:01:58,210 --> 00:01:58,540
Right?

35
00:01:58,540 --> 00:02:00,820
So when n is given we have to find f of n.

36
00:02:00,820 --> 00:02:04,390
So this is the question now in the interview.

37
00:02:04,390 --> 00:02:09,100
If you do have any questions about this question you have to ask clarifying questions.

38
00:02:09,100 --> 00:02:12,850
Now over here I'm just proceeding because this is a classic question.

39
00:02:12,850 --> 00:02:13,210
Right.

40
00:02:13,210 --> 00:02:16,090
So you may have already encountered this question.

41
00:02:16,090 --> 00:02:19,870
And we will solve this problem in multiple ways.

42
00:02:19,870 --> 00:02:23,650
And we will try to learn different concepts by solving this question.

43
00:02:23,650 --> 00:02:24,880
Now let's proceed.

44
00:02:24,880 --> 00:02:29,200
So we have established that what we need to write is a function where n is given.

45
00:02:29,200 --> 00:02:30,820
And we need to find f of n.

46
00:02:30,820 --> 00:02:35,260
And it's given that when n is equal to zero, then the value is zero.

47
00:02:35,260 --> 00:02:40,630
When n is equal to one, the value is one, and then this is the value when n is equal to two, and

48
00:02:40,630 --> 00:02:43,840
this is the value when n is equal to three and it goes on like that.

49
00:02:43,840 --> 00:02:44,350
All right.

50
00:02:44,350 --> 00:02:45,640
So let's proceed.

51
00:02:46,710 --> 00:02:52,020
To start with, let's just write out the Fibonacci series to get a good understanding of the Fibonacci

52
00:02:52,050 --> 00:02:52,350
series.

53
00:02:52,350 --> 00:02:57,570
And this is a very famous series, and Fibonacci is the mathematician who introduced this.

54
00:02:57,600 --> 00:02:58,140
All right.

55
00:02:58,140 --> 00:03:00,870
So it's given that the first two terms are zero and one.

56
00:03:00,870 --> 00:03:04,890
And we get the next term by adding up these two terms.

57
00:03:05,010 --> 00:03:08,100
So zero plus one that gives us one which is the next term.

58
00:03:08,100 --> 00:03:11,610
And to get the next term we have to add these two terms.

59
00:03:11,610 --> 00:03:14,070
So one plus one which is equal to two.

60
00:03:14,100 --> 00:03:15,300
So that's the next term.

61
00:03:15,300 --> 00:03:17,730
Again we have to add one and two to get three.

62
00:03:17,730 --> 00:03:19,110
So that's the next term.

63
00:03:19,110 --> 00:03:23,130
And then we add two and three right two and three to get five.

64
00:03:23,130 --> 00:03:24,510
And it goes on like this.

65
00:03:24,510 --> 00:03:24,690
Right.

66
00:03:24,690 --> 00:03:26,310
So three plus five is eight.

67
00:03:26,580 --> 00:03:29,010
And then we get eight plus five is 13.

68
00:03:29,010 --> 00:03:31,080
Eight plus 13 is 21.

69
00:03:31,080 --> 00:03:32,160
And it goes on like that.

70
00:03:32,160 --> 00:03:35,850
So that's the Fibonacci series and it goes on till infinity.

71
00:03:35,880 --> 00:03:40,020
Now over here we are asked to write a function where n is given.

72
00:03:40,020 --> 00:03:41,820
And we have to find f of n.

73
00:03:41,820 --> 00:03:47,310
Now it's also given that when n is equal to zero, we take f of zero which is zero.

74
00:03:47,310 --> 00:03:48,570
So this is f of zero.

75
00:03:49,720 --> 00:03:50,200
All right.

76
00:03:50,200 --> 00:03:53,650
And it's, uh, what else is given?

77
00:03:53,650 --> 00:03:55,060
Let's just write the in.

78
00:03:55,060 --> 00:03:55,510
Right.

79
00:03:55,510 --> 00:04:00,280
Let me just make some space over here so that we can understand what the output should be.

80
00:04:00,280 --> 00:04:02,170
So let me just write n over here.

81
00:04:03,380 --> 00:04:07,460
Now, when n is equal to zero, f of n is zero.

82
00:04:07,460 --> 00:04:08,660
When n is equal to four.

83
00:04:08,660 --> 00:04:14,000
For example, f of four is equal to three, right and f of eight would be 21.

84
00:04:14,000 --> 00:04:18,320
So when f when n is equal to one, f of one is nothing but one.

85
00:04:19,670 --> 00:04:19,940
Right.

86
00:04:19,940 --> 00:04:21,170
Which is this value over here.

87
00:04:21,170 --> 00:04:23,390
Similarly, when n is equal to eight.

88
00:04:23,420 --> 00:04:25,880
F of eight will be equal to 21.

89
00:04:26,960 --> 00:04:29,090
So this is the function that we need to write.

90
00:04:29,090 --> 00:04:35,120
So we've got a good idea about the Fibonacci series and the function that we need to write.

91
00:04:35,120 --> 00:04:37,610
We are given n and we need to find f of n.

92
00:04:37,610 --> 00:04:40,340
And remember f of zero is zero.

93
00:04:40,340 --> 00:04:41,540
This is f of zero.

94
00:04:42,290 --> 00:04:46,070
This is f of one, this is f of eight, etc..

95
00:04:46,160 --> 00:04:47,510
Now let's go ahead.

96
00:04:47,510 --> 00:04:51,230
And in the next section let's discuss how we can solve this.

97
00:04:51,230 --> 00:04:54,260
And we will discuss multiple ways of solving this problem.

98
00:04:54,260 --> 00:04:59,240
And we will discuss the time and space complexity of different ways of solving this question.