1
00:00:00,640 --> 00:00:01,540
Welcome back.

2
00:00:01,540 --> 00:00:04,570
Let's now think how we can solve this question.

3
00:00:04,570 --> 00:00:08,680
Now to start with, let's just walk through an addition of two numbers.

4
00:00:08,680 --> 00:00:13,570
Let's say we want to add 628 and 567.

5
00:00:13,570 --> 00:00:18,520
Now how would we do it normally first we would add eight and seven and we get 15.

6
00:00:18,520 --> 00:00:22,330
So we write five over here and one is going to be carry forward.

7
00:00:22,330 --> 00:00:24,520
Now we add one two and six.

8
00:00:24,520 --> 00:00:26,380
And that's going to be equal to nine.

9
00:00:26,380 --> 00:00:28,810
And then we add six and five.

10
00:00:28,810 --> 00:00:30,190
So that's equal to 11.

11
00:00:30,190 --> 00:00:32,590
So we write one over here and one over here.

12
00:00:32,590 --> 00:00:35,200
So this is actually a carry forward this one over here.

13
00:00:35,200 --> 00:00:36,790
But because there is nothing over here.

14
00:00:36,790 --> 00:00:38,590
So we just write this one over here.

15
00:00:38,590 --> 00:00:40,930
So that is how we have the normal addition right.

16
00:00:40,930 --> 00:00:42,370
So everyone is aware of this.

17
00:00:42,370 --> 00:00:46,330
Now let's try to think how we can implement this in our code.

18
00:00:46,330 --> 00:00:47,770
And we are using the linked list.

19
00:00:47,770 --> 00:00:49,450
So we have these two linked lists.

20
00:00:49,450 --> 00:00:52,330
We have eight pointing to two pointing to six.

21
00:00:52,330 --> 00:00:55,540
And then we have seven pointing to six pointing to five.

22
00:00:55,540 --> 00:01:00,100
Now over here you can see that we actually start adding from the units digit over here.

23
00:01:00,100 --> 00:01:04,990
So it's actually in our advantage that the linked lists are in the reverse order.

24
00:01:04,990 --> 00:01:06,760
Now what can we do over here.

25
00:01:06,760 --> 00:01:08,020
We have to add these two.

26
00:01:08,050 --> 00:01:11,890
So what we do is first let's take these two values.

27
00:01:11,890 --> 00:01:14,080
So that's the head of the two linked list.

28
00:01:14,080 --> 00:01:16,420
So we get eight over here and seven over here.

29
00:01:16,420 --> 00:01:17,560
Now let's add them.

30
00:01:17,560 --> 00:01:18,790
So we get eight plus seven.

31
00:01:18,790 --> 00:01:20,080
That's equal to 15.

32
00:01:20,080 --> 00:01:25,390
Now let's we over here we have seen that we actually want only the unit digit over here.

33
00:01:25,390 --> 00:01:25,660
Right.

34
00:01:25,660 --> 00:01:31,900
So to get this what we can do is we will take this 15 and then we will do percentage ten or modulo ten.

35
00:01:31,900 --> 00:01:38,530
So that will give us the remainder when 15 is divided by ten which is actually this digit over here.

36
00:01:38,530 --> 00:01:41,110
So by doing this we will get the value five.

37
00:01:41,560 --> 00:01:44,620
Now let's take this five and make a node.

38
00:01:44,620 --> 00:01:47,350
And we make it the head of the output linked list.

39
00:01:47,350 --> 00:01:48,790
So we have five over here.

40
00:01:49,030 --> 00:01:52,420
Now we also need to check whether there is any carry forward.

41
00:01:52,420 --> 00:01:53,740
Now how do we do that.

42
00:01:53,740 --> 00:01:56,260
So for that let's take this 15.

43
00:01:56,680 --> 00:02:03,640
And let's divide this by ten and floor it like for example if you take this 15 and we divide it by ten

44
00:02:03,640 --> 00:02:05,380
we will get 1.5.

45
00:02:05,650 --> 00:02:11,950
Now if we floor this or round it down right, this will become equal to one which is actually this number

46
00:02:11,950 --> 00:02:12,400
over here.

47
00:02:12,400 --> 00:02:14,410
And that is what will be carry forward.

48
00:02:14,410 --> 00:02:14,680
Right.

49
00:02:14,680 --> 00:02:18,730
So we can do floor of 15 divided by ten which is equal to one.

50
00:02:18,730 --> 00:02:20,410
And that is the carry forward.

51
00:02:20,410 --> 00:02:20,830
All right.

52
00:02:20,830 --> 00:02:22,900
So let's make a note of the carry forward.

53
00:02:22,900 --> 00:02:24,760
So we will just write it over here.

54
00:02:24,760 --> 00:02:27,220
So we have one over here which is the carry forward.

55
00:02:27,220 --> 00:02:28,600
Now let's proceed.

56
00:02:28,600 --> 00:02:30,340
So we are done with these two nodes.

57
00:02:30,340 --> 00:02:33,400
So we are going to move ahead in both these linked lists.

58
00:02:33,400 --> 00:02:35,140
So over here we get two.

59
00:02:35,140 --> 00:02:37,180
And then over here we get six.

60
00:02:37,180 --> 00:02:40,120
Again we take these two values and we add them.

61
00:02:40,120 --> 00:02:42,820
And then we add the carry forward also along with this.

62
00:02:42,820 --> 00:02:46,540
So two plus six plus one gives us nine.

63
00:02:46,540 --> 00:02:46,840
Right.

64
00:02:46,840 --> 00:02:48,010
So that's equal to nine.

65
00:02:48,010 --> 00:02:49,810
Now we take this nine.

66
00:02:49,810 --> 00:02:53,080
And then we are going to take percentage ten or modulo ten on it.

67
00:02:53,080 --> 00:02:55,600
So that's the remainder when nine is divided by ten.

68
00:02:55,600 --> 00:02:57,280
So that gives us nine itself.

69
00:02:57,280 --> 00:03:00,610
So we take this value and we are going to make a node out of it.

70
00:03:00,610 --> 00:03:03,190
And this is made to point to the next node.

71
00:03:03,190 --> 00:03:03,640
All right.

72
00:03:03,640 --> 00:03:06,670
And then we have to check whether there is a carry forward or not.

73
00:03:06,670 --> 00:03:11,590
Now we know that there is no carry forward over here, but in the code to check whether there is a carry

74
00:03:11,590 --> 00:03:12,400
forward or not.

75
00:03:12,400 --> 00:03:16,720
All that we need to do is we need to divide nine by ten and then floor it.

76
00:03:16,720 --> 00:03:18,700
This is the same thing that we did previously.

77
00:03:18,700 --> 00:03:22,060
So when we divide nine by ten we will get 0.9.

78
00:03:22,060 --> 00:03:27,610
And when we floor it that becomes zero which means that the carry forward is equal to zero.

79
00:03:28,090 --> 00:03:28,510
All right.

80
00:03:28,510 --> 00:03:30,130
So we have got these two nodes.

81
00:03:30,130 --> 00:03:31,060
Let's proceed.

82
00:03:31,060 --> 00:03:34,720
So we are going to move ahead in these two linked lists which is given to us.

83
00:03:34,720 --> 00:03:36,700
So over here we have six.

84
00:03:36,700 --> 00:03:38,830
And over here we have five.

85
00:03:38,830 --> 00:03:41,080
Again let's go ahead and add these two.

86
00:03:41,080 --> 00:03:42,370
And there is no carry forward.

87
00:03:42,370 --> 00:03:44,680
So six plus five is equal to 11.

88
00:03:44,680 --> 00:03:49,180
Now let's try to learn or understand what value to take over here.

89
00:03:49,180 --> 00:03:51,850
When we make a node for this we are going to take this 11.

90
00:03:51,850 --> 00:03:54,550
And again we will do percentage ten or modulo ten.

91
00:03:54,550 --> 00:03:58,510
And that gives us the remainder when 11 is divided by ten which is equal to one.

92
00:03:58,510 --> 00:04:01,000
So we are going to take this value one over here.

93
00:04:01,000 --> 00:04:03,640
And then we will make a node with this value.

94
00:04:03,640 --> 00:04:05,830
And then we will make nine point to this.

95
00:04:06,220 --> 00:04:06,640
All right.

96
00:04:06,670 --> 00:04:09,040
Now let's check whether there is a carry forward over here.

97
00:04:09,040 --> 00:04:10,690
For this we take this 11.

98
00:04:10,690 --> 00:04:13,300
And let's just divide it by ten and floor it.

99
00:04:13,300 --> 00:04:16,900
So if we do this when we do 11 by ten we will get 1.1.

100
00:04:16,900 --> 00:04:20,620
And when we floor it we will get one which is this value over here.

101
00:04:20,620 --> 00:04:20,860
Right.

102
00:04:20,860 --> 00:04:22,690
And we can see that's the carry forward.

103
00:04:22,690 --> 00:04:23,260
All right.

104
00:04:23,260 --> 00:04:24,880
So there is a carry forward of one.

105
00:04:24,880 --> 00:04:26,890
So let's just make a note of it over here.

106
00:04:27,760 --> 00:04:28,090
All right.

107
00:04:28,090 --> 00:04:29,290
So we have one over here.

108
00:04:29,770 --> 00:04:31,510
And then we are going to move forward.

109
00:04:31,540 --> 00:04:35,440
Now when we move forward we see that in these two linked lists right.

110
00:04:35,440 --> 00:04:36,370
We have null.

111
00:04:36,910 --> 00:04:38,320
We have null and null over here.

112
00:04:38,320 --> 00:04:43,600
So when we add whatever values are there over here there is just this carry forward over here which

113
00:04:43,600 --> 00:04:44,680
is equal to one.

114
00:04:44,680 --> 00:04:48,790
Now again let's take one percentage ten one modulo ten.

115
00:04:48,790 --> 00:04:49,660
That gives us one.

116
00:04:49,660 --> 00:04:50,980
So we take this value one.

117
00:04:50,980 --> 00:04:52,420
And we make a node out of it.

118
00:04:52,420 --> 00:04:55,420
And we make this one point to this node over here.

119
00:04:55,420 --> 00:04:57,790
Again we are going to check if there is a carry forward.

120
00:04:57,790 --> 00:04:58,360
For this.

121
00:04:58,390 --> 00:05:00,760
We will do one divided by ten.

122
00:05:00,760 --> 00:05:01,900
And then we are flooring it.

123
00:05:01,900 --> 00:05:03,490
And that gives us zero right.

124
00:05:03,490 --> 00:05:05,080
One by ten is 0.1.

125
00:05:05,080 --> 00:05:11,050
And when we floor it we will get zero which means that there is no carry forward and hence we can stop.

126
00:05:11,050 --> 00:05:13,420
So this is how we can solve this question.

127
00:05:13,420 --> 00:05:19,420
And the interesting thing that you have to notice over here is we have to keep iterating through the

128
00:05:19,420 --> 00:05:25,390
linked list, as long as there is an element in either of the linked lists, or if there is something

129
00:05:25,390 --> 00:05:26,470
in the carry forward.

130
00:05:26,470 --> 00:05:28,360
So that is the that is very important.

131
00:05:28,360 --> 00:05:33,010
Alright, so even if there is no node in both the linked list, still, if there is a carry forward

132
00:05:33,010 --> 00:05:37,330
we need to keep iterating because still over here you can see we have to make one more node.

133
00:05:37,330 --> 00:05:40,420
So this is something very important which you should not miss.

134
00:05:40,420 --> 00:05:40,960
All right.

135
00:05:40,960 --> 00:05:42,760
So this is how we will solve this question.

136
00:05:42,760 --> 00:05:47,290
Now let's take a quick look at the space and time complexity of this solution.

137
00:05:47,290 --> 00:05:49,780
Now let's first look at the time complexity.

138
00:05:49,780 --> 00:05:56,320
What would be the number of operations that we have to do now over here we have seen that we had to

139
00:05:56,320 --> 00:05:57,850
go through the linked list.

140
00:05:57,850 --> 00:05:58,000
Right.

141
00:05:58,000 --> 00:05:59,440
We have to traverse the linked list.

142
00:05:59,440 --> 00:06:02,350
So let's say both the linked lists are of different length.

143
00:06:02,350 --> 00:06:07,750
It could be that we have one linked list which has let's say four elements and one linked list which

144
00:06:07,750 --> 00:06:08,830
has just two elements.

145
00:06:08,830 --> 00:06:12,190
Now in this case we would have to go through the longer one.

146
00:06:12,190 --> 00:06:12,460
Right.

147
00:06:12,460 --> 00:06:19,180
So we can say that the time complexity is equal to of the order of the length of the longer linked list.

148
00:06:19,300 --> 00:06:19,720
All right.

149
00:06:19,720 --> 00:06:22,450
So if both of them are the same then it would be the same.

150
00:06:22,450 --> 00:06:26,050
But let's say one is of length m and one is of length n.

151
00:06:26,050 --> 00:06:32,020
Then we can say that the time complexity is of the order of maximum between m and n.

152
00:06:32,730 --> 00:06:33,090
All right.

153
00:06:33,120 --> 00:06:35,400
Now, what about the space complexity?

154
00:06:35,430 --> 00:06:40,560
You can see that we do take up space because we have to return the output as a linked list.

155
00:06:40,560 --> 00:06:42,660
So this is going to take up space right.

156
00:06:42,660 --> 00:06:44,520
So we have to make a new linked list.

157
00:06:44,520 --> 00:06:47,310
Now the size of this linked list.

158
00:06:47,310 --> 00:06:53,010
The new linked list the maximum possible size is going to be the length of the longer linked list plus

159
00:06:53,010 --> 00:06:53,580
one right.

160
00:06:53,580 --> 00:06:58,830
For example, in this case you can see both of these linked lists are of size three and this linked

161
00:06:58,830 --> 00:07:01,560
list over here the output linked list is of size four.

162
00:07:01,560 --> 00:07:04,890
So you can have plus one over here if there is a carry forward.

163
00:07:04,890 --> 00:07:08,760
So this is the maximum possible length of the output linked list.

164
00:07:08,760 --> 00:07:14,310
So we can say that the space complexity is going to be of the order of the length of the longer linked

165
00:07:14,310 --> 00:07:18,270
list, which is the same thing which we got for the time complexity as well.

166
00:07:18,270 --> 00:07:19,920
So again, we can write it in this manner.

167
00:07:19,920 --> 00:07:25,290
Also, space also is going to be of the order of the maximum between M and N.