In this video, we're going to solve this cutting interview question single number in this problem given
in non empty area of integers nums.
In this area every element appears to eight except for one.
Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra spit.
This is the problem statement.
In this problem we're given an array of integers and in that area we have every element appears to it
except one, and we have to find out the single one.
In this example, this area.
In this area we see two appears twice and one appears once.
So we have two region one in this example we see one appears twice to appear to part of appears one.
So we have two written for and for this example we have only one element.
Disillusioned appears one.
So we have to return this element.
Now how to solve this problem.
We have a constraint.
We have to solve this problem in linear runtime complexity and our algorithm should works in constant
split.
First, let's talk about the brute force solution.
In the brute force solution.
What I will do first I will construct a set that a structure lets I do this each hour set the structure
in this said did a structure out store the non repetitive element.
That means that the element that appears only once.
But how we're going to do that.
First thing, we have to traverse this area from left to right.
First we have four weeks before doesn't exist.
So let's insert here for now we have one.
One does not exist.
Never said two.
Let's insert here one now two two does not exist.
So let's insert two in our set.
Now we have one and we set it just in our how set.
So what I will do, I'll just remove one.
Now we have the element two.
We see two appears in this set to exist.
So we'll remove this two.
So let's remove this two.
Now we see that we have only one element in our set and this is the single element.
This element appears only once in the given area.
So we have to return this element.
This is how we can solve this problem using hash sit data structure.
Now let's implement this algorithm.
Now let's implement the brute force algorithm first thing.
What we're going to do, we're going to check if the length of the error is one.
It means that we have only one element in the array.
We should return that element.
So written nums is zero.
Now let's create a hash set data structure.
So set we'll store integer.
Let's call it said equals to new heights it.
Now we have to iterate the array from left to right.
So for entirely close to zero I lived in nam stored lint I plus plots inside here all going to check
if the current element contains in our city.
Then you'll remove the current element from set, so let's check it.
Said DOT contains if if the current element contains in our set sonam's enum now your current element.
If our current element contains in the set, then it will remove from set.
So say do not remove nums i.
Otherwise, if if the element does not exist in our set, we will add the element to our set.
So say did add nums a.
When we're done with this fall off, we will have only one element in our set so we can retain that
element.
For that, I have to use this statement set dot, iterator, dot.
Next we have to iterate over the grid, over the set, edit it over the set.
We will get all the element just in the set.
We have only one element in the set for sure.
So we can we can just return, said Dot.
Next, this algorithm will takes off in time, complexity and off in space complexity.
Now let's run this code.
Accepted.
Now let's submit it.
We have successfully solved this problem.
But this is a brute force algorithm.
We have a constraint to this problem.
We have to solve this problem in constant in constant space complexity.
Can you solve this problem in constant space?
Complexity.
Now, let's see how to improve this space complexity to constant space complexity.
Let's assume we're given this array of integers in order to solve this problem in a constant space complexity
we had to use XOR operator.
We know for sure in the area we have some element appears tweet and only one element appears once.
So we can use exert operator.
We know the operation for two same bit it result in zero if we have to number here exert e it's results
in zero if we apply exert operation in between, do same number, it will result in zero.
Okay.
This is the properties of exert operator.
If we have something like this here exert zero, then it will be result in a again this is zero naught.
Oh, we can solve this problem using the concept of XOR operator.
Now what we will do will iterate the array from left to right and we'll applied the exit operator for
old element.
Something like this.
First trip to.
So to endure to.
And then we will have one.
So to exit to its result in zero.
Okay.
So we get here 001.
So we get to 001001 equals two one.
This is it.
The element that appears only once in the area.
So we have to return this element.
Now, let's assume you're given this array of integers.
Now let's apply exit operations in between all the numbers in the given array.
So we have, for example, one for exer one exer to exert one, then exert two.
Now what we see in here, we have two one.
So one, one.
It will be evaluated zero.
And we have it to two.
It will be evaluated zero.
So for zero.
For these two, it will be evaluated as zero.
Then exert is zero.
Now for these two.
This comes from this welcome for this two and two.
No 000 is zero.
So four exerts zero four exert.
Zero equal to for.
This is the answer, and this element appears only once in the given area.
So this is the single element or single number in the given area.
This is the answer.
This algorithm will take off in time complexes in which we have to traverse the array from left to right,
and it will take speed of one.
This space complexity, since we're using just one variable.
Now let's see how to implement this algorithm.
No, let's implement this algorithm.
First, let's create a variable entry codes to the first element.
We'll get the first element if we live in this area for one, two, one, two.
We have two records to first eliminate.
That means for now we have to iterate the array from the second index.
So for intake holds to one i liz then nums dot lint i plus plot.
No.
Here, we have to.
We have to apply to exert operations in building all the numbers.
Okay.
So answer equals to answer, exert numbers, height.
And at the end, every region the answer you'll have the answer in this answer variable.
How it works.
Initially we have Anthony calls to four.
Then if we apply this for love, then we get four, exert one, exert to exert one, exert two.
So here this two and this two will be able to do zero.
So we have zero.
If we apply here zero and one will have the result one.
Then the excellent between one and one is zero.
We know the extrapolation in between same number result in zero.
So the extrapolation in between four and zero is four.
And this is our single number in this area.
That means this number appears only once.
This algorithm will takes bigger off in time complexity and it will takes bigger of one space complexity
because we're using just one variable answer and let's around this code, it's accepted.
Now let's submit it.
We solved this problem, maintaining the constraint, linear time and constant spits.
Thanks for watching this video.
I will see you in the next video.