Welcome back.
We have seen in the previous video that we can solve this question and find the duplicate number by
converting this to a linked list question.
So let's say this is the array which is given to us four, three, one, two and three.
The indices are zero, one, two, three four.
Now zero over here is pointing to four.
All right.
So I have zero pointing to four.
And then we have index four over here.
So among this four and this four I'm just writing four over here because we are treating these two as
the same.
So zero is pointing to four.
Now four is pointing to three.
So we write three over here.
So three and this is three over here.
Now three is pointing to two.
So we have two over here.
And then two is pointing to one.
And one is again pointing to three.
So we can see that we have a cycle over here which is starting at the node with value three.
So that's why we can identify that three is the repeating number.
Now let's go ahead and code this.
So for this let's write a function and we can call it get duplicate.
Now this function is going to take in the array.
And let's call this array numb's.
Now inside the function, let's have the hare and tortoise.
So initially both of them are going to be equal to zero.
So hare is equal to zero and tortoise is equal to zero.
All right.
This means that both of them are at index zero over here in the beginning.
Now we are going to have a while loop.
And we know that there is a loop.
Right.
So it's given that one number is repeating.
So definitely there will be a loop.
So we will keep looping.
As long as the hare and tortoise have not met.
And we will come out when they have met.
And once they have met we will go ahead and proceed and identify where they have started, where the
cycle starts.
And for this we are using the Floyd's Hare and Tortoise algorithm.
So let's go ahead.
Now the hare is going to move two steps.
Now over here.
What is two steps.
Let's try to observe it.
It's one step is going from 0 to 4 right.
So four over here is numb's at zero or numb's at hare.
So Numb's at hare.
This is one step right.
So from 0 to 4.
So numb's at here and here is equal to zero gives us four.
So that's one step.
Now we just have to move one more step so we can say numb's at this value over here.
So numb's.
At Numb's at here.
So this is how the hair will move.
Two steps.
All right.
So numb's at here is four and numb's at four gives us three.
So the hair is going from 0 to 3.
And the tortoise is moving only one step.
So the tortoise is going to be equal to numb's at tortoise.
So initially the tortoise is at zero and numb's at zero gives us four.
So from 0 to 4.
So the tortoise is moving one step.
All right.
So these keep moving in this manner.
Now we will check if the hare and tortoise have met.
So if hare is equal to tortoise.
Now, the remaining part of whatever we're going to do in the while loop will only happen when the hare
and tortoise meet.
So when they meet, we should have a pointer established at the head and at the meeting point and in
in the meeting point, as we have discussed in the question where we discussed the Floyd's Hare and
tortoise algorithm, we will use the tortoise pointer itself.
All right.
Now once they have met.
So let's have a pointer.
So we'll say let pointer.
And the pointer is going to point at the head.
And the head of this linked list is index zero.
So pointer is equal to zero.
And now the pointer and the tortoise will keep moving one step as long as they have not met.
So while pointer.
Not equal to tortoise.
As long as this is the case, the pointer will move one step.
So pointer is going to be equal to numb's at pointer.
And the Toto is also will move one step.
So Toto is equal to Numb's at tortoise.
All right, so once we come out of this while loop, the pointer and the tortoise have met.
So over here they would be meeting at the starting point of the cycle.
And then we can just return that particular value so we can just return the pointer.
All right.
And the pointer will be the value three.
So this is how we can solve this question.
Let's now test our code.
Now for this let's call our function get duplicate.
And let's pass in the same array over here.
Now the array is four, three, one, two and three.
Now let's run our code and see what's happening.
All right.
You can see we're getting three, which is the repeating value over here.
Now let's just test a few more cases.
What if we have, um, let's say we have more numbers.
Let's say we have five also.
And let's say this is the same thing.
So again we run it and again it's working right now.
What if we have um, uh, five repeating two times.
So we should be getting five.
And you can see we're getting five.
So yes, our code is working.
Now what about the space and time complexity?
The space and time complexity is the same as the space and time complexity of the Floyd's Hare and Tortoise
algorithm.
Now over here you can see we keep moving, right?
The tortoise is in the worst case will move completely throughout the cycle once it will not start looping,
right.
So before the tortoise goes ahead from one, they would have met.
So we have discussed that in the Floyd's Hare and tortoise algorithm part.
So the time complexity of this solution is going to be O of N, and the space complexity is constant
space.
Because we are not using any auxiliary space to come up with the solution.