1
00:00:00,240 --> 00:00:01,800
Hi, everyone, welcome back.

2
00:00:01,980 --> 00:00:07,890
So in this video, we are going to solve this very important question, the beat and the missing numerary,

3
00:00:08,490 --> 00:00:08,850
right?

4
00:00:09,090 --> 00:00:11,650
So let me explain you what is the problem statement?

5
00:00:12,000 --> 00:00:15,060
So let's take one example.

6
00:00:15,270 --> 00:00:15,750
Yep.

7
00:00:15,960 --> 00:00:16,740
Let's do this.

8
00:00:17,310 --> 00:00:18,360
So what do we have?

9
00:00:19,420 --> 00:00:25,650
First of all, it is given that the array's read-only area, that means you cannot change the revalues

10
00:00:25,650 --> 00:00:30,270
rate and it is containing and integers starting from one, two and.

11
00:00:30,960 --> 00:00:32,159
Right, fine.

12
00:00:32,430 --> 00:00:39,240
Now, what happening is each integer appeared exactly once rate one integer is coming only one time.

13
00:00:39,240 --> 00:00:40,320
Exactly one time.

14
00:00:40,530 --> 00:00:46,530
But there is one integer A which is coming twice and there is one integer B which is not present.

15
00:00:46,890 --> 00:00:52,560
And we need to find out the value of A and B, let's try to take this example and let's try to understand

16
00:00:52,830 --> 00:00:58,310
that so all the values are between one, two, five, eight.

17
00:00:58,920 --> 00:01:05,960
So this is a read-only area and assizes five synthesisers five that size is five.

18
00:01:05,970 --> 00:01:08,350
So all the values will be between one, two, five.

19
00:01:08,760 --> 00:01:10,750
So in ideal situation, what should happen?

20
00:01:11,490 --> 00:01:13,050
This should be the error content.

21
00:01:13,050 --> 00:01:14,340
One, two, three, four, five.

22
00:01:14,430 --> 00:01:15,200
Northshore data.

23
00:01:15,210 --> 00:01:21,000
Basically, it can be in any order, but it is given that all the elements only from one to N and each

24
00:01:21,000 --> 00:01:22,560
element will appear exactly once.

25
00:01:22,890 --> 00:01:24,410
So this is the ideal scenario.

26
00:01:24,420 --> 00:01:27,910
This is what we want right in the question.

27
00:01:27,930 --> 00:01:32,370
It is saying that number is coming twice and the number B is missing.

28
00:01:33,010 --> 00:01:35,450
That means the addresses will not be changed.

29
00:01:35,460 --> 00:01:35,840
Right.

30
00:01:36,530 --> 00:01:43,590
So in this case, we can see elementary is coming twice, Elementalist coming twice.

31
00:01:43,620 --> 00:01:45,120
So that is our element.

32
00:01:46,020 --> 00:01:48,270
And Element B is missing.

33
00:01:48,450 --> 00:01:50,460
So element four is missing, right?

34
00:01:50,670 --> 00:01:54,210
Element three is coming place and element four is missing.

35
00:01:54,330 --> 00:01:58,530
So basically this forward is going is replaced by three.

36
00:01:58,710 --> 00:01:59,000
Right.

37
00:01:59,320 --> 00:02:01,710
So that's why the addresses will remain same.

38
00:02:01,890 --> 00:02:08,520
So what we need to do, we need to find out what is A and what is B, we need to find out the value

39
00:02:08,520 --> 00:02:09,900
of these two variables.

40
00:02:11,520 --> 00:02:13,200
So now how we can do this.

41
00:02:14,070 --> 00:02:16,690
So it's going to be actually very, very simple.

42
00:02:16,710 --> 00:02:20,770
So first, let us talk about the very simple approach.

43
00:02:21,150 --> 00:02:24,660
So what we can do, we can maintain when map.

44
00:02:26,290 --> 00:02:33,160
And in this map module, we will have given loopier key will be our integer, basically the error rate

45
00:02:33,550 --> 00:02:36,340
and the value will be decode that is also integer.

46
00:02:36,340 --> 00:02:39,730
So value is count how many times this element is coming.

47
00:02:39,730 --> 00:02:41,670
And integer is basically every element.

48
00:02:41,680 --> 00:02:42,040
Right.

49
00:02:42,520 --> 00:02:44,290
So every element.

50
00:02:46,220 --> 00:02:52,760
So what I will do, I will I try to watch this every night, so the first element is three, OK, three,

51
00:02:52,760 --> 00:02:54,850
the count is one and this is our map.

52
00:02:56,390 --> 00:02:59,360
So for three, the count is one element one.

53
00:02:59,360 --> 00:03:00,680
So insert element one.

54
00:03:00,860 --> 00:03:02,360
And this is coming for the first time.

55
00:03:02,360 --> 00:03:03,260
So count this one.

56
00:03:03,680 --> 00:03:04,880
Next element is two.

57
00:03:05,150 --> 00:03:10,870
So two is coming for the first time and it's count this one next element is five.

58
00:03:11,090 --> 00:03:12,890
So five is coming for the first time.

59
00:03:12,890 --> 00:03:17,720
So its value, its count is basically one now three is coming again.

60
00:03:17,720 --> 00:03:19,370
So three is already presenting the map.

61
00:03:19,370 --> 00:03:24,530
So I will increase its count to two and then we will reach the end of the error rate.

62
00:03:24,740 --> 00:03:30,020
So we have our map ready map of the area element and its count.

63
00:03:30,680 --> 00:03:35,060
So what we will do now, we will migrate from one to five.

64
00:03:36,290 --> 00:03:41,120
We will trade from one to five because the addresses is five.

65
00:03:41,570 --> 00:03:45,920
So I'm going to iterate from one to five now for element one.

66
00:03:46,340 --> 00:03:47,600
I will check each count.

67
00:03:47,720 --> 00:03:49,820
So element one count is one fine.

68
00:03:50,210 --> 00:03:51,470
Now, element two.

69
00:03:51,800 --> 00:03:55,640
So element to count is one fine element.

70
00:03:55,750 --> 00:03:59,540
Three counties to count is two.

71
00:03:59,540 --> 00:04:01,970
That means I got to know my first number.

72
00:04:02,210 --> 00:04:11,090
I got to know what is a so it is three eight three is appearing twice now the next element for the four

73
00:04:11,090 --> 00:04:19,519
is not present in map four is not present in map and that it so be is for now the last element.

74
00:04:19,519 --> 00:04:20,570
Five so five.

75
00:04:20,570 --> 00:04:21,380
The count is one.

76
00:04:21,380 --> 00:04:22,010
That's fine.

77
00:04:22,340 --> 00:04:25,550
And we will reach the end of the loop and we know the value of it.

78
00:04:25,550 --> 00:04:28,820
We know the value of B and we can return these two values.

79
00:04:29,960 --> 00:04:30,530
Simple.

80
00:04:30,830 --> 00:04:33,800
Now what is the time and the space complexity.

81
00:04:34,190 --> 00:04:35,390
So time, complexity.

82
00:04:35,390 --> 00:04:37,760
Let's first discuss about time, complexity.

83
00:04:38,000 --> 00:04:43,400
So what you are doing, you need to iterate over this area to insert all the values into the map.

84
00:04:43,820 --> 00:04:44,200
Right?

85
00:04:44,330 --> 00:04:51,110
So time complexity is big often and then you need to iterate over these from one to five and to check

86
00:04:51,110 --> 00:04:51,680
in map.

87
00:04:51,680 --> 00:04:58,940
So and plus N that is to win and one is same as big often if you talk about the space complexity.

88
00:04:59,960 --> 00:05:06,890
So you need to create one map and this map will be our size and it will contain maximum an element.

89
00:05:07,100 --> 00:05:14,270
So this is the time, the space complexity for using this method using the map approach, which is fine.

90
00:05:14,750 --> 00:05:16,760
Now let's discuss this second approach.

91
00:05:17,360 --> 00:05:20,900
So the second approach basically involves a little bit of maths.

92
00:05:21,230 --> 00:05:22,040
So what do you do?

93
00:05:22,190 --> 00:05:24,050
What is the sum of area?

94
00:05:25,070 --> 00:05:26,570
It will be some value, right?

95
00:05:27,170 --> 00:05:29,470
We will trade over this area and we'll find out the sum.

96
00:05:29,480 --> 00:05:30,710
So it will be some value.

97
00:05:31,550 --> 00:05:31,970
Fine.

98
00:05:32,180 --> 00:05:36,650
Now, we also iterate from one to five, so that will also be some value.

99
00:05:37,040 --> 00:05:42,080
So let's call it this is area and this value is basically expected value.

100
00:05:43,550 --> 00:05:44,990
This is expected value.

101
00:05:46,490 --> 00:05:52,340
Fine, so can we find out the relation between these two values, what will be the relation between

102
00:05:52,340 --> 00:05:53,160
these two values?

103
00:05:53,360 --> 00:05:56,070
So I think what is some of Eddie?

104
00:05:58,330 --> 00:06:06,550
So basically, if you find out the expected does same from one to five, if you find out the sum from

105
00:06:06,550 --> 00:06:14,690
one to five and you subtract four and if you add three, right.

106
00:06:14,890 --> 00:06:17,220
So in this case, element four is not present.

107
00:06:17,230 --> 00:06:19,630
I want to find this value from this.

108
00:06:19,930 --> 00:06:21,760
So element four is not present.

109
00:06:21,770 --> 00:06:26,490
So that's why you need to subtract four and elementary is coming twice.

110
00:06:26,680 --> 00:06:28,170
So that's why you are adding three.

111
00:06:29,500 --> 00:06:34,390
So that means this will be the relation between these two weight.

112
00:06:34,540 --> 00:06:37,100
Subtract B and add A, right.

113
00:06:37,120 --> 00:06:37,730
That's fine.

114
00:06:38,050 --> 00:06:41,340
Now it will do some Wolfberry.

115
00:06:42,640 --> 00:06:44,340
And what does this expected.

116
00:06:44,350 --> 00:06:44,580
Some.

117
00:06:44,590 --> 00:06:47,770
This is your sum from one to and.

118
00:06:47,980 --> 00:06:48,400
Right.

119
00:06:48,730 --> 00:06:51,670
So take it to the left hand side.

120
00:06:51,700 --> 00:06:53,620
So this will be some expected.

121
00:06:53,620 --> 00:06:57,900
That is some from one twin and that is minus B plus here.

122
00:06:57,940 --> 00:06:59,560
Or we can write A minus B.

123
00:07:00,550 --> 00:07:03,460
So this is our first equation right now.

124
00:07:03,460 --> 00:07:08,260
What we can do, I can also find one more thing, which is every square.

125
00:07:10,720 --> 00:07:12,450
So what is some added square?

126
00:07:12,460 --> 00:07:19,960
So some square means three squared plus one squared plus two squared plus five squared plus again,

127
00:07:19,960 --> 00:07:20,480
three square.

128
00:07:20,680 --> 00:07:22,780
So I'm not adding the value simply.

129
00:07:22,780 --> 00:07:25,270
I am first squaring the value and then I am adding.

130
00:07:25,480 --> 00:07:26,650
So that is what it is.

131
00:07:26,650 --> 00:07:27,020
Square.

132
00:07:27,490 --> 00:07:30,380
So the square will be exactly the same relation.

133
00:07:30,700 --> 00:07:32,230
So here is what you will do.

134
00:07:32,260 --> 00:07:37,090
You will do one squared plus two squared, plus three square and so on and square.

135
00:07:37,990 --> 00:07:39,260
And this is a minus.

136
00:07:39,440 --> 00:07:41,710
So this will be squared minus B squared.

137
00:07:42,590 --> 00:07:43,030
Right.

138
00:07:44,160 --> 00:07:46,410
OK, so let's try it again here.

139
00:07:46,450 --> 00:07:49,930
This is some elements squared.

140
00:07:51,970 --> 00:07:56,930
Minus some one square deal and square.

141
00:07:57,520 --> 00:07:59,320
So what is A square, minus B square?

142
00:07:59,350 --> 00:08:05,840
So we have the formula for this that is minus B in to A plus B, right.

143
00:08:06,730 --> 00:08:09,850
So now here this is our second equation.

144
00:08:10,900 --> 00:08:15,130
So we know the value of minus B, that we know the value of minus be.

145
00:08:15,850 --> 00:08:22,180
So if we will divide by A minus B, then you will get the value of here plus B, right.

146
00:08:22,480 --> 00:08:26,380
So some add A square.

147
00:08:30,620 --> 00:08:40,370
Minus some one square deal and square and this whole divided by the value of A minus B and the value

148
00:08:40,370 --> 00:08:41,900
of minus B, this one.

149
00:08:42,409 --> 00:08:50,270
Right, so divided by A minus B, and that will be A plus B, so you know the value of minus B, you

150
00:08:50,270 --> 00:08:55,470
know this value, you know this value and for the minus B, you know this value and you know this value.

151
00:08:55,670 --> 00:09:03,200
So basically you know the value of A plus B, so this is your third equation or let's remove this and

152
00:09:03,200 --> 00:09:04,460
this is your second equation.

153
00:09:04,970 --> 00:09:05,210
Right.

154
00:09:05,510 --> 00:09:06,950
So now you have two equation.

155
00:09:06,950 --> 00:09:09,760
This is equation one and this is equation two.

156
00:09:10,040 --> 00:09:13,610
So you have two equations and you have two variables.

157
00:09:14,240 --> 00:09:14,580
Right.

158
00:09:15,040 --> 00:09:17,420
So you have two equations and two variables.

159
00:09:17,750 --> 00:09:21,360
So you can easily find out the value of A and B, how.

160
00:09:21,800 --> 00:09:29,540
So if you add equation one and two, if you add equation one plus equation to what will happen, B and

161
00:09:29,540 --> 00:09:32,540
B, they will cancel out each other because this is negative.

162
00:09:32,540 --> 00:09:33,620
B, this is positive.

163
00:09:33,620 --> 00:09:34,660
B, right.

164
00:09:34,850 --> 00:09:36,870
So you will get to know the value of it.

165
00:09:37,190 --> 00:09:43,220
And if you know the value of it, you can put the value of in this equation or in this equation to find

166
00:09:43,220 --> 00:09:44,750
out the value of B right.

167
00:09:44,870 --> 00:09:45,530
Very easy.

168
00:09:46,070 --> 00:09:52,000
So what we will do in next video, I will write the code for this problem using the mathematical approach.

169
00:09:52,430 --> 00:09:57,240
Try implementing the mathematical approach to yourself or you can whichever solution with you.

170
00:09:57,830 --> 00:10:00,120
So in next video, I will be writing the code.

171
00:10:00,170 --> 00:10:01,750
So this is it from this revised.

172
00:10:01,760 --> 00:10:03,150
I will see you in the next one.

173
00:10:03,170 --> 00:10:03,740
Thank you.