Hi, everyone.
So today we are going to solve this question single no.
OK, so what is the problem statement?
So no statement is very clear.
So we will be given.
So the input will basically be Eddie.
I ready and we have to do so, basically, every element will appear twice inside the area except for
one element, and our task is to basically find that one element.
OK, so let us consider some example.
So this is our input today.
So, see, every element is appearing twice except one element.
So this is orcharding only one time.
So our answer for this input will basically be one.
OK, now C two is updating two times when is appearing two times.
So forward is the element that we have to find.
So in this case, our answer will be four, because every element is appearing twice except one element.
And we have to find this one element.
OK, now let see this example.
So one is appearing two times, two is appearing two times.
So I have this elementally, so these are being only one time.
So our answer will be three.
OK, so I hope you understood the question.
Now let's discuss the approaches to solve this question.
OK, let's discuss approach number one.
OK, so first approach is basically it involves sorting.
OK, so what we will do, so we will sort the area.
OK.
So after sorting the area, what will happen?
So let us consider this example.
OK.
So this area will become one to two.
So basically what will happen?
So if the elements are slim, they will appear in a decent manner.
OK, so in this case, I will to over the area and I can see when is the different element.
OK, so first I will start the area and then I will iterate over the area.
So what is the time and the space complexity.
So spaces will be are drawn and time is first.
I am starting the area so and Logan and then I armatrading out the area which is then.
So basically this is nothing but.
And Logan.
OK, similarly, if you will sort this out.
So what will happen, all the elements which are the same, they will appear in the they will come in.
They are designed to be OK.
So this idea will become one one, two, two and four.
So basically, when you illustrate they are saying move overhead, they are saying move now.
This is the different element.
OK, so in this way, you can find out the element now for this area, if you will apply the starting
approach, what will happen?
So this will be one one, then again to two and then three.
OK, so these two elements are same.
These tremendous him.
This is occurring one time.
OK, so our answer will be this.
So in this way, what we will do first start theory and then to find out the answer and just outraged
over the error and find the unique element.
OK, so this is the time and the space complexity time and again.
And space complexity is basically one.
OK, so now let us discuss the second approach.
So the second approach, basically it is it uses Hashmat.
OK, so in the second approach, what we do so basically in the second approach we will create a hash
map.
OK, so what we'll do, we will take a map.
OK, so the key will be element.
And the value will be basically the account of that element.
OK, so this is the key value that I will totally Hashmat.
OK, so now let's just iterate over the array.
So let us consider this example.
OK, four, one, two, one, two.
So I have for one again, two, one and two.
OK, so initially my map is empty.
Now I trade so I have a limit for its count.
This one.
Then I have element one.
So element one, it's count this one, then I have two.
So I have element to then it's count this one, I have element one.
So increase the count so it will become two.
I have this element also includes the count.
It will become too.
OK, so once you will iterate over the array you hash map is ready.
I would be ready.
Then what we will do we will trade over the hash map.
OK, we will trade over the hash map.
And if there is an element present whose count is basically one, then our answer will be basically
the key.
OK, so in this case I would answer well before because it's count this one.
OK, now let us consider one more example.
So suppose I have one, two, two, three and one.
Let us prepare our hash map.
OK, so I have this element when so when it's count this one.
OK, now element to its count this one again elemental.
So I will increase the count.
OK and I have elementary so push inside the hash map.
Count this one.
Now I have element one to increase the count.
OK, so after doing this our test prep is ready.
After reading over the area, I would have thought I was ready then I would like to over the map and
Guitry has gone to one, so that's why I would answer will be three.
OK, and similarly with this one, also, if you will prepare the hash map, it will be like element
to count one.
Then again, element also I will make the count to then I have element one to element one and count
this one.
So this is the Hashmat.
Now, I trade over the map and you will be able to find the answer, which is one.
OK, so in this case, what is the time and the space complexity?
So basically, time complexities big off, and so we are assuming that the unordered so we lose, we
will use in order to map.
And in order to map the time complexities, basically order of an OK, you can insert, you can search.
So all this time complexities are basically ordered offline.
OK, so the time complexity is just started off and we are trading over the edge and preparing the hash
map and the space complexities basically all that often.
OK, so this is the time and the space complexity for using the hash map.
OK, so you can see we are optimizing on time, but here we are using extra space.
Here we are using extra space to prepare the map.
OK, so now let us discuss the best approach for solving this question.
OK, so let's discuss approach number three.
So we have our approach.
So excited, overrated.
OK, so this is the symbol.
So what is also basically the timetable of SARS, so you have two values, and B, so if this is one
one one zero zero one and zero zero.
And this is basically the output.
OK, so what they are doing, why is basically A, X or B, OK, so when you will apply the operator,
what will happen?
So if the elements are same, then the output will be zero.
So in this case, the elements are same, the output is zero.
And if the elements are different and output is one.
OK, so this is what, Exodus?
OK, so suppose is basically two and basically three, so what will happen?
So this is a bitwise operator.
So how bitwise operators will work, so it will convert to into its binary form, so which is basically
one in zero, will convert three into its binary form, which is nothing but one and one, and then
we will apply the exact operator.
So the elements are different.
Output is one element, the same.
So the output.
And now we will convert this binary into its decimal form.
So it will become one.
OK, so basically two zah two exactly.
Is nothing but one.
OK, so this is how it works.
Now there are some properties of XOL.
OK, so what are those properties.
So in order to solve this question you must know those properties.
So the first properties supposed to have an element A.
So the first properties, if you will, or two same elements, you will get zero second property, so
you have an element and if you will take the order with zero, then you will get itself.
OK, so this is the first property.
This is the second property.
So third property is basically the XOR operator is basically associative.
OK, so if you will write like this A, X or B, X or A, then basically and this, and this will be
zero.
OK, you can see if the elements are same, they are zero.
So what you can write so e x or B x ray.
This is nothing but a X or A, X or B.
OK, and this will become zero.
So I have zero X or B and then we will use the second property.
So this is nothing but B.
OK, so you can write A, X or B, X or so, and they will cancel out each other, you will have B,
OK, so these are the three properties that you should know.
OK, so these are the first two properties and this one is the third property.
Now, let's see how we can use this extra body to solve our question.
OK, so let us take some examples.
So for one, two, one, two, OK, so I have this idea for one, two, one, two.
So this is for this is one.
This is two.
This is one.
And this is two.
OK, what we will do so we will take the XOR off all the elements, take X out of all the elements.
So what it will look like for X or one X or two X or one expert to.
OK, so what will happen.
This one and this one, they will cancel out each other, these two and this, they will cancel out
each other.
Why.
They will cancel out each other.
Because I know e if the elements are sim and I'll take the third output will be zero and if you will
take the Zord with zero you will take you will get itself.
OK, so what will happen.
Only four will be the remaining element.
So our answer will be for.
OK, let us consider one more example, so.
I have one, then I have two, I have two and three and one.
Now, let's take XOR of all the elements of the.
So what it will look like when X to X to excite three Akhavan.
OK, so this two and these two will cancel out each other.
This one will cancel out this one.
So our output will be three.
OK, so very simple.
So what did be the time this was complexity of using this approach, so space complexity will be a rough
one.
OK, and the time complexity will be what we are doing.
We are just outrating over the.
So the time complexity will be big of an.
OK, so this is the best approach.
OK, this is the best approach.
So what we will do, we will take a variable.
Initially that variable will be zero and then we will take the zoref old element.
OK, this has to be zero.
OK, this has to be zero because what will what do you will write.
You will write like something.
So answer equals answer x or let's say the name of that is a aof.
OK, so basically when the value of zero, that is the first element, so that's why you have to initialize
with the zero because you can see this is the property zero X or any element is basically that element
only.
OK, so you have to initialize your answer with zero.
This is compulsory.
OK.
Now that that's right, the good.
So basically, this is a legitimate problem.
OK.
So now let us write the code.
OK, so let's change the name of that to be a so we have to return that integer that is appearing only
one time.
So first, let us create a variable answer.
Which will contain that unique element and this has to be initialized with zero.
OK, so now what we have to do, we are just iterating over the Eddie.
So Edward says.
Now you just have to take the XOR of all the elements, OK, you just have to take the eggs out of all
the elements.
And finally, what you look, you will return, I would answer.
OK, so what I'm doing here.
So let us consider this example for one, two, one, two.
OK, so I have four.
One, two, one, and then two.
So this is one.
OK, so my answer is initially zero.
OK, our answer is initially zero, then I will take the action with the first element so it will become
zero or four.
So this is basically for then I will take the I will take the Tzavela one element.
So this is for X or one.
So this is basically for X or Y and only then I will take the Zoref two.
So this is for X or one and then two.
OK, so this is the value of one.
So you can see answer operator error element.
So this is the answer.
This is the operator and this is the element.
OK, so then I will take XOR with one.
So what is the answer?
The answer is for actual one X or two.
OK, so this is the answer, then the operator and then the area element, which is when now what will
happen.
This one and this one, they will cancel out each other.
So this is basically for X or two, OK, and then this element to.
So our answer will be, which is the current answer to our current answer is, for example.
Then the operator, Exide operator, and then the element of the too, so this two and these two, they
will cancel out each other.
So basically when we will come out, so I will reach here.
So basically, we will come out of this for loop surveillance that will contain food, which is the
right answer, and we will return that answer.
OK, very simple.
Now let us submit our code.
OK.
OK, so our goal is working fine, so let us summarize, so basically.
So basically we have discussed three approaches for solving this question.
First approach was basically desalting approach.
That time, complexity was basically and Logan.
And this space complexity was hard enough when.
The second approach that we discussed, it involves the use of Hashmat.
OK, the time complexity we discussed was big off and and the space complexity was also a big off.
And so we can see here we are improving all the time, but we are taking more space.
OK, now, the third way that the third way to solve this question is basically with the help of our
operator.
OK, the time complexity is basically big off and and the space complexity is basically big of one.
OK, so this is the best approach for solving this question.
OK, and what are the properties of X or so any element.
Exide with the same element, output will be zero.
Any element Exurbia zero basically will be that element only, and the third basically is the associative
property.
So A, X or B, X or A is basically nothing.
It is same as a X or a Asabi.
So this will become zero.
So I have zero X or B and this is nothing but B, OK, so in short you can ride this and disable, cancel
out each other.
Your output will be.
OK, so I hope you understood this question.
Thank you.