Welcome back.
Now let's go ahead and discuss how we can approach this question.
Now again, remember, the things that is mentioned in the question is that we are given an array and
it has n plus one integers, and the integers in the array will be from one to n, and both of them
are inclusive and there is exactly one integer repeating itself.
Now let's try to develop some intuition regarding how we can solve this question.
Now let's take an example for this.
Let's say the array which is given to us is 14323.
So you can see that the numbers over here are in the range 1 to 4 and one and four is included.
And then over here we have five integers right.
So n is equal to five.
All right.
Now let's go ahead and write the indices of the array.
So we have 0123 and four.
All right.
So let's take this example over here.
And let's make some space.
All right.
Now over here it's given that n is equal to five right.
So n is equal to five.
And again we're trying to develop our intuition.
And the range of the integers in the given array is 1 to 4 because n is five over here.
And we know that exactly one integer only will repeat itself.
So this means that the numbers one, two, three, four have to occur exactly at least one time, right?
Not exactly one time, at least one time.
And one number has to occur one more time, which is the number which is repeated.
So for example, over here you can see one two, three four occur and then three is repeated.
Right.
So that's the case because we need five numbers.
And we can only use the numbers 1 to 4.
So this will be four numbers.
So to get to five numbers one of them has to repeat.
So at least one of them.
But in the question it is mentioned that exactly one is repeated.
So we can be sure that 123, four will occur at least one time and one number will be repeated.
And that's how we are getting five numbers.
All right.
Now again let's take a look at the indices over here which we have written.
So we can see that in the indices we have zero.
And then we have 1234 which is the same thing that we have over here as well.
All right.
Now let's try to use this information to come up with the method to solve this question.
Now what if we treat these values over here in the array as indices itself.
Right.
Because we can see that the indices have the same values as the values that we have in the array.
All right.
So what if we treat these values over here as indices.
If we do that then we can convert this question to a cycle detection question in a linked list.
Let's try to draw it out and further develop our intuition.
So again over here we have our example.
Now this is zero.
So let's just write this zero over here.
And again what is it that we are trying to do.
We are going to treat these values over here as indices itself.
So zero is pointing to one.
So we have the value one over here.
So let's say zero is pointing to one.
And at one we have the value four.
Right.
So zero is pointing to one.
So this is one and this is one.
So I'm treating these two as the one and the same thing.
So zero is pointing to one.
So let me just write that over here.
So zero is pointing to one.
And then over here we have one.
And at one we have one is pointing to four.
Right.
So one is pointing to four.
So this four is what I'm going to write over here.
So one is pointing to four.
And then over here we have four.
And four is pointing to three.
Right.
So four is pointing to three.
So let's write that three over here.
Now at index three we have the value two.
So three is pointing to two.
All right.
So three is pointing to two.
And then at index two again we have the value three.
So two is pointing to three.
So we have a cycle over here.
All right.
Now you can see that this is our singly linked list and zero is pointing to one.
One is pointing to four, four is pointing to three, three is pointing to two, and two is again pointing
to three.
Now again, one more interesting thing to observe over here zero is pointing to one.
So I have these two ones right.
So I'm just treating that as this one over here.
And one is pointing to four.
Again four is pointing to three.
So this four and this four is one.
And the same thing and four is pointing to three.
So that's how we get this over here.
So this is how we have converted this into a singly linked list.
Now also notice that the cycle over here is starting at the value three over here.
And that is the repeated value.
We can see three is repeating two times.
And that's the repeated number.
So this is how we can solve this question.
And again because we're just detecting a cycle in a linked list.
And we know we have earlier discussed Floyd's hare and tortoise algorithm.
So we know how to do this in constant space without modifying the array.
Right.
We are not modifying the array because we don't need to go ahead and even we don't need to use extra
space because we're not going to create this singly linked list using extra space.
Right?
All we are going to do is that we are going to treat this array over here as a linked list.
So what do I mean with that.
So let's just discuss that as well.
So over here I have zero.
Now this one over here is nothing.
But if I call this array let me just call this array Numb's.
All right.
So this one over here is nothing but numb's at zero.
Now this for over here is nothing but numb's.
At numb's.
At zero.
Right.
Because numb's at zero gives me one and Numb's at one gives me four.
So you can see we don't need to use up extra space and create the singly linked list.
We can just treat the given array as a singly linked list in this manner.
All right so one is numb's at zero and four is numb's at numb's at zero.
All right.
So let's now go ahead.
Now we have established this.
We have established how we can treat this question and convert this question into a cycle detection
question in a singly linked list.
And if we can just find where the cycle starts, we will be able to find the repeated number.
Now, we have already discussed how we can find a cycle in a singly linked list using Floyd's Hare and
tortoise algorithm.
Let's quickly revise that over here.
So we have the hare and tortoise both at the head initially.
Now the hare is going to move two steps at a time, and the tortoise is going to move one step at a
time.
So let's see that.
So the hare comes over here and the tortoise comes over here.
In the next iteration the hare again moves one step and the the hare moves two steps and the tortoise
moves one step.
So the hare comes over here and the tortoise is over here.
And this continues.
Right.
So again the tortoise moves and the hare moves.
So the hair moves one step to two steps.
So the hare is again over here itself.
And in the next step you can see the tortoise and the hare both meet over here right.
So the tortoise is over here and the hare is over here.
So this is the meeting node.
Now we know how we can find the beginning of the cycle if we know the meeting point.
Right.
So for this we will need a pointer at head at the head which is zero over here.
So our pointer is going to point to zero.
And then we are going to again use the tortoise pointer over here.
And both the pointer and the tortoise is now going to move one step at a time till these two meet.
So the pointer moves.
And the hare or the tortoise also moves.
And again the pointer moves and the tortoise moves.
Again the pointer moves.
And the tortoise also moves.
And you can see both of them are meeting at three.
And that is the beginning of the cycle.
And again for our purpose this is the repeated value.
So this is how we will solve this question.
Now let's take a quick look at the time and space complexity of this solution.
Now it's going to be the same time and space complexity which we have discussed for Floyd's Hare and
Tortoise algorithm.
Now over here, the maximum number of movements that the tortoise is going to make is going to be having
the upper bound of n, right.
Because we have seen that the tortoise before, the hare and tortoise is going to meet, they are not
going to, um, come.
Right.
They're not the tortoise is not going to enter the cycle.
So to identify their meeting point, we would want at most n operations.
And then we will have another some operations which again can be treated as a multiple of n for the
pointer and the tortoise to meet.
So overall it's just a constant into n.
So we can say the time complexity is of the order of n right.
Because again we have to identify the beginning point.
And the space complexity is constant space because you're not using up any extra space.