Hi, everyone, welcome back.
So in this video, we are going to solve this very important question, the beat and the missing numerary,
right?
So let me explain you what is the problem statement?
So let's take one example.
Yep.
Let's do this.
So what do we have?
First of all, it is given that the array's read-only area, that means you cannot change the revalues
rate and it is containing and integers starting from one, two and.
Right, fine.
Now, what happening is each integer appeared exactly once rate one integer is coming only one time.
Exactly one time.
But there is one integer A which is coming twice and there is one integer B which is not present.
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
that so all the values are between one, two, five, eight.
So this is a read-only area and assizes five synthesisers five that size is five.
So all the values will be between one, two, five.
So in ideal situation, what should happen?
This should be the error content.
One, two, three, four, five.
Northshore data.
Basically, it can be in any order, but it is given that all the elements only from one to N and each
element will appear exactly once.
So this is the ideal scenario.
This is what we want right in the question.
It is saying that number is coming twice and the number B is missing.
That means the addresses will not be changed.
Right.
So in this case, we can see elementary is coming twice, Elementalist coming twice.
So that is our element.
And Element B is missing.
So element four is missing, right?
Element three is coming place and element four is missing.
So basically this forward is going is replaced by three.
Right.
So that's why the addresses will remain same.
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
of these two variables.
So now how we can do this.
So it's going to be actually very, very simple.
So first, let us talk about the very simple approach.
So what we can do, we can maintain when map.
And in this map module, we will have given loopier key will be our integer, basically the error rate
and the value will be decode that is also integer.
So value is count how many times this element is coming.
And integer is basically every element.
Right.
So every element.
So what I will do, I will I try to watch this every night, so the first element is three, OK, three,
the count is one and this is our map.
So for three, the count is one element one.
So insert element one.
And this is coming for the first time.
So count this one.
Next element is two.
So two is coming for the first time and it's count this one next element is five.
So five is coming for the first time.
So its value, its count is basically one now three is coming again.
So three is already presenting the map.
So I will increase its count to two and then we will reach the end of the error rate.
So we have our map ready map of the area element and its count.
So what we will do now, we will migrate from one to five.
We will trade from one to five because the addresses is five.
So I'm going to iterate from one to five now for element one.
I will check each count.
So element one count is one fine.
Now, element two.
So element to count is one fine element.
Three counties to count is two.
That means I got to know my first number.
I got to know what is a so it is three eight three is appearing twice now the next element for the four
is not present in map four is not present in map and that it so be is for now the last element.
Five so five.
The count is one.
That's fine.
And we will reach the end of the loop and we know the value of it.
We know the value of B and we can return these two values.
Simple.
Now what is the time and the space complexity.
So time, complexity.
Let's first discuss about time, complexity.
So what you are doing, you need to iterate over this area to insert all the values into the map.
Right?
So time complexity is big often and then you need to iterate over these from one to five and to check
in map.
So and plus N that is to win and one is same as big often if you talk about the space complexity.
So you need to create one map and this map will be our size and it will contain maximum an element.
So this is the time, the space complexity for using this method using the map approach, which is fine.
Now let's discuss this second approach.
So the second approach basically involves a little bit of maths.
So what do you do?
What is the sum of area?
It will be some value, right?
We will trade over this area and we'll find out the sum.
So it will be some value.
Fine.
Now, we also iterate from one to five, so that will also be some value.
So let's call it this is area and this value is basically expected value.
This is expected value.
Fine, so can we find out the relation between these two values, what will be the relation between
these two values?
So I think what is some of Eddie?
So basically, if you find out the expected does same from one to five, if you find out the sum from
one to five and you subtract four and if you add three, right.
So in this case, element four is not present.
I want to find this value from this.
So element four is not present.
So that's why you need to subtract four and elementary is coming twice.
So that's why you are adding three.
So that means this will be the relation between these two weight.
Subtract B and add A, right.
That's fine.
Now it will do some Wolfberry.
And what does this expected.
Some.
This is your sum from one to and.
Right.
So take it to the left hand side.
So this will be some expected.
That is some from one twin and that is minus B plus here.
Or we can write A minus B.
So this is our first equation right now.
What we can do, I can also find one more thing, which is every square.
So what is some added square?
So some square means three squared plus one squared plus two squared plus five squared plus again,
three square.
So I'm not adding the value simply.
I am first squaring the value and then I am adding.
So that is what it is.
Square.
So the square will be exactly the same relation.
So here is what you will do.
You will do one squared plus two squared, plus three square and so on and square.
And this is a minus.
So this will be squared minus B squared.
Right.
OK, so let's try it again here.
This is some elements squared.
Minus some one square deal and square.
So what is A square, minus B square?
So we have the formula for this that is minus B in to A plus B, right.
So now here this is our second equation.
So we know the value of minus B, that we know the value of minus be.
So if we will divide by A minus B, then you will get the value of here plus B, right.
So some add A square.
Minus some one square deal and square and this whole divided by the value of A minus B and the value
of minus B, this one.
Right, so divided by A minus B, and that will be A plus B, so you know the value of minus B, you
know this value, you know this value and for the minus B, you know this value and you know this value.
So basically you know the value of A plus B, so this is your third equation or let's remove this and
this is your second equation.
Right.
So now you have two equation.
This is equation one and this is equation two.
So you have two equations and you have two variables.
Right.
So you have two equations and two variables.
So you can easily find out the value of A and B, how.
So if you add equation one and two, if you add equation one plus equation to what will happen, B and
B, they will cancel out each other because this is negative.
B, this is positive.
B, right.
So you will get to know the value of it.
And if you know the value of it, you can put the value of in this equation or in this equation to find
out the value of B right.
Very easy.
So what we will do in next video, I will write the code for this problem using the mathematical approach.
Try implementing the mathematical approach to yourself or you can whichever solution with you.
So in next video, I will be writing the code.
So this is it from this revised.
I will see you in the next one.
Thank you.