I always start out by watching random stuff for a break and always end up studying because I either feel guilty for not being productive enough or bc it's a topic I'm interested in. Some ppl just can't escape
@@defalt7732 OMG!! I'm caught 😅😅 I can't be guilty of this... 😭😭 But yeah I can't JUST thank him cuz he has put efforts to explain it though he doesn't really have to.
Some additional info for Method 3 for who was struggling like me: - Notice that in the algorithm, after the hare and the tortoise meet at M in the cycle, we move the hare back to the beginning, then the hare and the tortoise moves 1 step at a time now. - We want them to both meet at the beginning of the cycle now. Why? Because that proves that there are 2 Nodes that have the same number (the node just to the left of the cycle, and the node that close the cycle). Which proves the main problem. Now: - The hare has to take x steps to get from the beginning to reach the cycle. - The tortoise also move x steps in that time. Our hope is that they will meet at the beginning of the cycle after x steps. How do we know that they will meet again after x steps? The hare is stepping from the beginning, the tortoise is stepping inside the cycle, right? To know how, notice the reason why he proves that z = x mod L, and this can be translated to x = kL + z. Basically, while the hare is walking outside in kL + z steps to reach the beginning of the cycle; the tortoise also loops in the cycle k times, goes back to the old meeting point M, then moves z more steps to go to the beginning of the cycle. And they meet. Sorry for being lengthy.
Okay I am starting to get it now. Intuitively it means that even if there is a big distance, for the reset pointer to cover, the one stuck in the loop will stay aligned with it and just cycle, and they will still meet at the same point.
I still don't get something. How is the cycle constructed? I understand the logic behind the detection and the modulo math for finding the start of the cycle. But how is the cycle constructed in the first place? Isn't this an array?
@@snooglemunch We treat elements of the initial array as "pointers" to the other elements. So if an element at index 3 has the value of 5, that means it points to the element at index 5. Element at index 5 has a different value so it points to the next index etc. When you draw it as a graph you get what's shown in the video. If two elements of the initial array have the same value, that means they point to the same element/node in the graph. The node that has two elements pointing to it is the one we're looking for. (for example, if the number 3 appears twice in the array that means there are two elements pointing to that element, which translates to two links going into that node on the graph, creating a cycle)
It's literally named Floyd's cycle-finding algorithm, so I'd assume that it only serves that niche purpose. I'd assume you can use it to prevent yourself from revisiting a node when traversing a list as a result of cycles, but I'd also assume there's better methods of doing such.
Well it’s already kind of a case of an algorithm that does one thing is being used for another problem. Floyd’s algorithm detects cycles, but the original problem was about finding duplicates in an array. It’s by reformatting the problem so that Floyd’s algorithm could be used that they’re able to solve it under the constraints.
This is a great explanation. I really liked the way you presented the content. I have been working on a proof that relies on fewer variables and tries to play a little more on intuition. Here it is: --- Let: T be the length of the tail (represented in the video by 'x') L be the length of the loop t be the number of steps the Tortoise has taken after it has entered the loop, starting from the loop's entrance. So at t=0 the Tortoise is at the loop's entrance, at t=1 the Tortoise is one node into the loop, at t=L the Tortoise is back at the loop's entrance, and so on. It follows that the "position" of the Tortoise in the loop is: t mod L. And, the position of the Hare at time t in the loop is: (T + 2t) mod L. The 2t in the above expression comes from the fact that the Hare travels twice as fast as the Tortoise. The T is there because it is the total distance in the loop the Hare has traversed at the time the Tortoise enters the loop. We know T is the distance the Hare traversed in the loop because at the time Tortoise entered the loop, the Tortoise traveled a total of T steps (including the tail), which means that the Hare traveled a total of 2T steps (it is twice as fast) - but the first T of those 2T = T + T steps were spent traversing the tail. So the rest of the T steps the Hare traveled in in the loop. So the meeting of the Tortoise and Hare will occur when: t mod L = (T + 2t) mod L Subtracting t and T from both sides we get: t mod L = -T mod L (These are valid operations since [a mod m = b mod m] if and only if [(a + k) mod m = (b + k) mod m] This tells us that the meet will occur at position: -T mod L. What is position "-T mod L"? It is the position in the loop we get to when we walk T steps backwards in the loop starting at the entrance. So the second part of the algorithm is correct since the pointer starting in the loop will be at the loop's entrance after walking T steps forward from the meeting point. --- Anyway, I hope to see more videos on this channel. Awesome work!
Why the algorithm worked wasn't my cause of confusion. What wasn't clear was how you apply this to the problem. It wasn't clear because the most obvious interpretation (which turned out to be right) had a pitfall: what if you immediately get caught in a cycle, like if the array starts with {1,2,...}? (It's a cycle if array indexing starts with 1) And then I realized that array indexing starts with 0 D; which prevents you from being in a cycle at the very start. This forces the graph to turn into the shape you assumed: a line leading into a cycle. ^I think you needed to add this into this video. It was also veeerrry roughly breezed over in the anime edition
I don't see why indexing starting from 0 makes it impossible to have a loop. even if all the numbers are unique, there can still be a place for a number in the array where it points to itself UPD: now I see it, it's impossible to have a number point at index 0 while being on index 0, then if it points elsewhere, the only way a number is pointing on itself would be it having a duplicate elsewhere. you just never find non-duplicate self pointers by going from 0 base
@@L1Q no it's totally possible to have a node point to itself. in graph terms, this is called a self-loop and self-loops can be modelled in code. for example: struct Node{ int val; struct Node* next; } Node starting_node; Node.next = &starting_node; this is a self-loop.
@@samuraijosh1595 ik i'm being nitpicky, but it seems like you're using C++, so your "Node.next" should actually be "Node->next", but great thing to point out nonetheless!
I don't see how this solves the original problem of finding the duplicate number, though. The array could easily have extra cycles that are unconnected to the duplicate entry. For instance [1, 0, 2, 2]. 0 and 1 form a cycle, but the duplicate entry is not included in that cycle.
Yeah, if the graph is not fully connected we might have a problem [probably the most frequent case]. But I think we can handwave that for the sake of comedy. And because the rest of the explanation is pretty cool.
Thanks Joma, I'll have to revisit this video again to grasp it completely but I tested out your code from repl and it worked really well. Coming from a non-math background my tests showed that the below simple code is only 2-3 times slower than floyd's algorithm for large arrays (10k items - 0.00015s vs. 0.00033s) and not orders of magnitude slower like when creating a set or sorting the initial array. nums = [1,3,4,2,2] for num in nums: if nums.count(num) > 1: print("Duplicate value is =", num) break
The proof is under the assumption that y > 0 if y = 0, then xmodL = 0, meaning x is a multiple of L, which implies the meeting point would be at the start of cycle, and the tortoise would still meet the new pointer at the start of cycle, so in the end everything still works out
Thank you very much!! I just started studying C, like, 4 hours ago, and got pretty happy to kinda understand the anime video an fully understand this one! Subscribed!
This would make way more sense if you just used actual numbers and physically showed the pointers moving. Then you could explain how the algorithm works in abstract with all sets of numbers following this rule set. The way it is now just begs more questions than it answers, and the model/visual aid becomes misleading. For people who are already half way there, it works. For everyone else it's just confusing.
I found this algorithm way before for finding out if a Linked List has a cycle. So I was surprised when I saw this same algo used on finding a duplicate number in an array.
@@zAlbee2 please explain why it works on [2,1,3,3] my brain tells me it would be stuck on number 1 (index 1) and think it's the solution. UPD: ok so the reason why [2,1,3,3] would still work is because we start from index 0 and jump directly to index 2, which contains value 3. this fixes both turtle and hare on index 3. holy shit this came to me. if a number is pointing to its own position it's basically out of the graph completely unless it's duplicate! genius! thank you Albert for giving a push in the right direction now I see the solution clearly AND understand why it works
Stumbled upon the channel because of anime video, like it so much so that look for this video for the explanation :D subscribed for the normal educational content
For the input set [2,1,4,3,4] The 2 and the 1 point to eachother, and the 4 and 3 also point to eachother. How does the algorithm deal with the case when the duplicate number is entirely outside of the loop that starts with index 0 ?
@18:36 L-Y is not the remainder of Y mod L after all the other Ls are gone. Rather we know that there is at least one complete loop by hare before it meets tortoise, so we rewrite (k*L - Y) mod L as (L - Y) mod L (since k cannot be zero) which is Z mod L which equals Z.
One flaw is that the turtle can travel multiple l, just like the rabbit, instead you use x+y. But basically, the whole idea is absolutely true! Nice one!
Here he told the hare runs twice as fast as tortoise But how does it explain Tortoise = nums[tortise] Hare = nums[nums[hare]] It doesn’t make sense how its twice as fast It just goes at the value of the index as a index
Tortoise = nums[tortoise] (I say node, but I just mean the position in the array.) The tortoise is a pointer to a node with an index and a value. The value is the index of the next node that it moves to. If tortoise is at a node with an index 0 and value of 2 (first element of array has index 0, it happens to have the value 2), then the tortoise pointer moves to the node with an index of 2 and some other value . Hare = nums[nums[hare]] The nums[hare] part is equal to the node with an index of what hare was before this statement and some value that’s the index of the next node (following the same logic as the turtoise). So now hare = nums[value of next node] will bring the hare’s pointer to the next-next node (compared to where it began)... yeah, you can tell I’m not good at explaining, but I hope this helps!
Jacky Chen Thanks I can understand that But my Question was how does it make it 2 times faster I thought it will b something like if the index is 2 then the next pointer will index 4 since it’s times 2 I can understand the logic of how it’s going But in the video he told it 2 times faster so I got confused of how exactly it’s 2 Where as it’s clearly not a multiple of 2 Thanks for the effort of explaining
So you can imagine nums[var] as getting the destination of the next step from the position var. Now, since we want to the hare to move twice, we could(alternatively) code it like this: 1step = nums[orgpos] 2step=nums[1step] However note that we can simply use substitution to simplify the code as 2step=nums[nums[orgpos]]
I proved this around the other way. First I started by modelling the distance the tortoise and hare are from the start at any point. Let k be the number of iterations that have occurred, d be the diameter of the cycle and i be the initial distance before the cycle (including the start of the cycle) let n1 be the number of times the tortoise has gone through the cycle and n2 be the number of times the hare has gone through the cycle. As the tortoise's distance increases by 1 each iteration and decreases by d every time it loops, it's distance will be k - n_1d. As the hare's distance increases by 2 every time and decreases by d every time it loops, it's distance will be 2k - n_2d. When the overlap, that means that T = H (where T = tortoise distance, H = hare distance). Therefore, at this point, k - n1d = 2_k - n_2d. Rearranging this, we find 2k - k = d(n_1 - n_2) or k = d(n_1 - n_2) Consider now k mod d. As n_1, n_2 are integers, and k = d(n_1 - n_2), k is a multiple of d, and thus k is congruent with 0 mod d. Our goal is to find the point at the beginning of the cycle as that's the point with in-degree 2 or more. (by definition, this will occur after a distance i as defined above) In this loop, we perform i iterations to reach our goal. this means the tortoise would have moved i times. This means the new tortoise position will be equal to T_i + i where T_i is the initial position of the tortoise. As T_i is congruent with 0 mod d, t_i + i is congruent with i mod d. As each point on the cycle is congruent with 1 distance mod d, two distances being congruent on the cycle implies they are at the same point, and thus the tortoise must be at the goal.
18:36 For the people like me who didn't understand this explanations, The reason why ( L + L + L ... - y ) modL equals "L - y", not equals to "- y " is if there's some subtraction operator in modular, we add one more mod value to avoid negative result. so... (k * L - y ) mod L is ( (k * L) mod L - y modL + L ) mod L. so.. like ( ( 10 * 3 ) - 4 ) % 3 is not equal -1, but 2. Thanks to this video, I finally realize why should I learn discrete mathematics..
The confusion for me was that the array isn't an arbitrary array of numbers. It's actually a linked list that can potentially go into a infinite cycle.
what is funny here is how everyone complains about hacking in movies but even when actual engineers write a story about hacking or programming they describe steps completely wrong for cinematic purposes
Just use set negative to the value index and use the abs of the value while you scan the array to check whether the value index is negative. If its negative it means it has duplication.
I almost commented on the equation but then I realised you were correct it's just the way you described it confused me. Anyways, well done, I really enjoy reading on mathematical algorithms and this one was really nice, I enjoyed watching the vid. I really enjoy the mathematical aspect of programming it's quite fascinating how mathematics is everywhere in our lives. Proves how idiotic it is to think mathematics is useless after school. Well, loved the vid.
(k*L) mod L = 0, but you put L above there So, I think there should be a correction. x mod L = (k*L - y) mod L = (0 - y mod L) = -(L-z) mod L = z mod L = z (z < L) Hence, x mod L = z WDYT?
It is not necessary to guarantee that the distance travelled by the turtle is gonna be x + y, except to prove that the algorithm is gonna take at most n steps to finish. If the turtle's distance was x + y + q*L(where q is the total loops the turtle does) then Hare distance = 2(x+y+qL) then 2(x+y) + 2qL = x + y + kL (k total loops the hare does) x = kL - 2qL - y x mod L = (L(k-2q) -y) mod L also k >= 2q since the hare can't do less loops than twice the loops the turtle does Then, x mod L = L - y mod L and so x mod L = z
U can get in a way like... There is a circular race track... Everyone starts with different speed.... They will meet again at there LCM of speed... Trying in linked list loop
What if the induced graph has multiple connected components (a.e. [2,3,1,5,6,5,5])? Starting in a wrong connected component means that you won't get a correct result, right? Am I missing something? Is this input illegal?
So, once we get X mod L means Z we have the starting point of the circle and decreasing by 1 we have the duplicate number, right? If I am right, then why don't we say the meeting point is the duplicate number? In the problem they didn't want positions of duplicate numbers. The just wanted the value which was written twice. Ain't that right? or we just need to make sure that duplicate numbers exist and we need to check arr[x-1]==arr[x+z]?
Yeah, so think about the indices from 0 to n being the nodes (the array has length n + 1). At each index/node, think of the value contained in the array as being the arrow into the next index/node. So the index in the array tells us the node, and the value at that index tells us the next index/node. Since there is a duplicate number in the array, two distinct nodes/indices in the array will point to the same index in the array. Our goal is to find the node that is pointed into by two different nodes. Now how do we find the node that is pointed into by two different nodes? Well, since we know that every value is between 1 and n, we know that the node at index 0 will point to an index/node within the range 1 to n in the array. We also know that once you get into the 1 to n range of the array, every next element will be within that range as well. Because of this, we know that if we start at node 0 and move forward, we will immediately reach the 1 to n range, and then once we're there, every node will point to some node within the same range, so we must have a cycle in that range. So we know that node 0 is not part of the cycle (since no node points into it due to the fact that all nodes point to nodes that are in the 1 to n range), but we also know that following node 0 will eventually lead us into the cycle. Because we can guarantee that we start without already being in the cycle, the node that starts the cycle will be pointed into by two different nodes (the node right before the cycle, and the last node in the cycle). But this is precisely what the goal I stated in the first paragraph was. So this entire algorithm is just to help us find the node that represents the start of the cycle, which must be pointed into by two different nodes/indices in the array, and hence must be the value that is duplicated.
@@Theactualstoic Wow, I'm so happy to hear that! I thought no one was going to read my answer, so I was just writing to solidify my understanding, but I'm so happy it was useful to you :D
An explanation about finding the entry point part. First assume when fast and slow meet, slow has moved a steps, and fast has moved 2a steps. They meet in the circle, so the difference a must be a multiple of the length of the circle. Next assume the distance between beginning to the entry point is x, then we know that the slow has traveled in the circle for a-x steps. How do we find the entry point? Just let slow move for another x steps, then slow will have moved a steps in the circle, which is a multiple of length of the circle. So we start another pointer at the beginning and let slow move with it. Remember x is the distance between beginning to the entry point, after x steps, both pointer will meet at the entry of circle.
6:03 Why do you use a set and not another array/list? You’re gonna fill n elements in the worst case scenario in both so is there an advantage in using a set?
I tested, it works but I didn't understand just why it does work. Thing I didn't understand is neither tortoise nor hare is following a regular sequence. For example in that anime video, code is used for 3,1,3,4,2 array if I am not wrong. In that example, tortoise goes from first element of array to fourth element of array then fifth element of array then thirth because the code is tortoise=nums[tortoise] and hare goes from first to fifth to fourth to thirth because the code is hare=nums[nums[hare]]. Tortoise doesn't go like 1 forward 1 forward 1 forward. It goes 3 forward 1 forward 2 back. I understood the math in these video and why x mod L = z but what exactly prooves x mod L = z and why? Can anyone help?
Hey Joma, I think creating a new channel about Algorithm was the right decision, I feel the Joma Tech channel is goingdown in many aspects, good luck to you !
array must be zero indexed, so at firs you must reach some index with value 1 to reach index 1, this means the duplicate number is 1, otherwise you can't reach index 1. it's not special case.
If yall had read the manga yall wouldnt need this explication
Lmaoooo
I mean Knuth is a great mangaka but he's been on hiatus forever, I can understand everyone's desire to just watch the adapted anime.
TBH I think some details are still missing... the LN was a lot nicer and I would recommend over the manga for sure.
Best comment I've read in a while lmaoo
if you read the light novel you could be the senpai teaching him this algorithm
1.4 million people: Watch a programming anime video just for fun.
36804 of them: I need that power!
Glad to be one of the 95,899.
Glad to be one of them
Glad of be one
Glad
Gla
I wanted to program it myself but I couldn’t, because of my carpal tunnel! Kuso!!!!
unlucky
If you had read the manga, you could be able to do it.
Try use voice to text
When a joking video had a good content
this is legendary
Senpai why you so fools 🤣
Just kidding
Was just randomly watching funny videos to relax. And now I’m here studying during my break time
Lol same
I always start out by watching random stuff for a break and always end up studying because I either feel guilty for not being productive enough or bc it's a topic I'm interested in. Some ppl just can't escape
Its 4 am trying to sleep
same bro 😂
yutube overestimated my intelligence once again by recomending this one
Bro, you got this.
Lol, you can do this. UA-cam algorithm will provide what it knows you can handle 😄
H
Thank you, Senpai!
Your comment made him to do this vid🤣 Tq
@@defalt7732 OMG!! I'm caught 😅😅
I can't be guilty of this... 😭😭 But yeah I can't JUST thank him cuz he has put efforts to explain it though he doesn't really have to.
Lol
Some additional info for Method 3 for who was struggling like me:
- Notice that in the algorithm, after the hare and the tortoise meet at M in the cycle, we move the hare back to the beginning, then the hare and the tortoise moves 1 step at a time now.
- We want them to both meet at the beginning of the cycle now. Why? Because that proves that there are 2 Nodes that have the same number (the node just to the left of the cycle, and the node that close the cycle). Which proves the main problem.
Now:
- The hare has to take x steps to get from the beginning to reach the cycle.
- The tortoise also move x steps in that time.
Our hope is that they will meet at the beginning of the cycle after x steps.
How do we know that they will meet again after x steps? The hare is stepping from the beginning, the tortoise is stepping inside the cycle, right? To know how, notice the reason why he proves that z = x mod L, and this can be translated to x = kL + z. Basically, while the hare is walking outside in kL + z steps to reach the beginning of the cycle; the tortoise also loops in the cycle k times, goes back to the old meeting point M, then moves z more steps to go to the beginning of the cycle. And they meet.
Sorry for being lengthy.
This is 4 months old but thx man
Okay I am starting to get it now. Intuitively it means that even if there is a big distance, for the reset pointer to cover, the one stuck in the loop will stay aligned with it and just cycle, and they will still meet at the same point.
Thank you. This comment is what got me to finally understand it.
I still don't get something. How is the cycle constructed?
I understand the logic behind the detection and the modulo math for finding the start of the cycle.
But how is the cycle constructed in the first place? Isn't this an array?
@@snooglemunch We treat elements of the initial array as "pointers" to the other elements. So if an element at index 3 has the value of 5, that means it points to the element at index 5. Element at index 5 has a different value so it points to the next index etc. When you draw it as a graph you get what's shown in the video. If two elements of the initial array have the same value, that means they point to the same element/node in the graph. The node that has two elements pointing to it is the one we're looking for. (for example, if the number 3 appears twice in the array that means there are two elements pointing to that element, which translates to two links going into that node on the graph, creating a cycle)
Thank you so much man! That video appeared in my recommendation yesterday and I was so confused... This video is much easier to understand.
Can you imagine another application for this algorithm? Because it seems pretty specific to this problem and these constraints
Not gonna lie, it’s pretty useless in real world applications.
@@JomaClass bruh
It's literally named Floyd's cycle-finding algorithm, so I'd assume that it only serves that niche purpose.
I'd assume you can use it to prevent yourself from revisiting a node when traversing a list as a result of cycles, but I'd also assume there's better methods of doing such.
Embedded hardware, SKU handling
Well it’s already kind of a case of an algorithm that does one thing is being used for another problem. Floyd’s algorithm detects cycles, but the original problem was about finding duplicates in an array. It’s by reformatting the problem so that Floyd’s algorithm could be used that they’re able to solve it under the constraints.
This is a great explanation. I really liked the way you presented the content.
I have been working on a proof that relies on fewer variables and tries to play a little more on intuition. Here it is:
---
Let:
T be the length of the tail (represented in the video by 'x')
L be the length of the loop
t be the number of steps the Tortoise has taken after it has entered the loop, starting from the loop's entrance.
So at t=0 the Tortoise is at the loop's entrance, at t=1 the Tortoise is one node into the loop, at t=L the Tortoise is back at the loop's entrance, and so on.
It follows that the "position" of the Tortoise in the loop is: t mod L.
And, the position of the Hare at time t in the loop is: (T + 2t) mod L.
The 2t in the above expression comes from the fact that the Hare travels twice as fast as the Tortoise. The T is there because it is the total distance in the loop the Hare has traversed at the time the Tortoise enters the loop. We know T is the distance the Hare traversed in the loop because at the time Tortoise entered the loop, the Tortoise traveled a total of T steps (including the tail), which means that the Hare traveled a total of 2T steps (it is twice as fast) - but the first T of those 2T = T + T steps were spent traversing the tail. So the rest of the T steps the Hare traveled in in the loop.
So the meeting of the Tortoise and Hare will occur when:
t mod L = (T + 2t) mod L
Subtracting t and T from both sides we get:
t mod L = -T mod L
(These are valid operations since [a mod m = b mod m] if and only if [(a + k) mod m = (b + k) mod m]
This tells us that the meet will occur at position: -T mod L.
What is position "-T mod L"? It is the position in the loop we get to when we walk T steps backwards in the loop starting at the entrance. So the second part of the algorithm is correct since the pointer starting in the loop will be at the loop's entrance after walking T steps forward from the meeting point.
---
Anyway, I hope to see more videos on this channel. Awesome work!
Why the algorithm worked wasn't my cause of confusion. What wasn't clear was how you apply this to the problem.
It wasn't clear because the most obvious interpretation (which turned out to be right) had a pitfall: what if you immediately get caught in a cycle, like if the array starts with {1,2,...}? (It's a cycle if array indexing starts with 1)
And then I realized that array indexing starts with 0 D; which prevents you from being in a cycle at the very start. This forces the graph to turn into the shape you assumed: a line leading into a cycle.
^I think you needed to add this into this video. It was also veeerrry roughly breezed over in the anime edition
Thank you for mentioning this! I was wondering about the 0th index and this makes perfect sense
When a comment blows your mind way more than the video
I don't see why indexing starting from 0 makes it impossible to have a loop. even if all the numbers are unique, there can still be a place for a number in the array where it points to itself
UPD: now I see it, it's impossible to have a number point at index 0 while being on index 0, then if it points elsewhere, the only way a number is pointing on itself would be it having a duplicate elsewhere. you just never find non-duplicate self pointers by going from 0 base
@@L1Q no it's totally possible to have a node point to itself. in graph terms, this is called a self-loop and self-loops can be modelled in code.
for example:
struct Node{
int val;
struct Node* next;
}
Node starting_node;
Node.next = &starting_node;
this is a self-loop.
@@samuraijosh1595 ik i'm being nitpicky, but it seems like you're using C++, so your "Node.next" should actually be "Node->next", but great thing to point out nonetheless!
1:17 he even gave a spoiler warning, such a cultured man
This was exactly the explanation I was looking for!
This is awesome I would love for you to do a series about learning algorithms! I always have huge problem with figuring how to build them!
bruh, this is helping me study and is making it the first leetcode medium I've solved. Whoever said anime wasn't useful?
thanks you for Floyd's Algorithm Explained
MORE ALGORYTHMS PLEASE! This was astounish entertaining
Belive i was just left wondering watching the anime video ,keep up these algorithm videos ❤
Oh my god thank you soooo much
Quality work as usual
I watched a few of these and didn't grasp it until I watched your mathematical explanation. Thanks.
I don't see how this solves the original problem of finding the duplicate number, though. The array could easily have extra cycles that are unconnected to the duplicate entry. For instance [1, 0, 2, 2]. 0 and 1 form a cycle, but the duplicate entry is not included in that cycle.
Yeah, if the graph is not fully connected we might have a problem [probably the most frequent case]. But I think we can handwave that for the sake of comedy. And because the rest of the explanation is pretty cool.
Numbers in the array are from 1 to n, it can't contain 0. I think this ensures that the duplicate is always in the cycle.
Thanks sir, this helped me last night to sleep after 2 days of no sleep. After I checked I fell asleep at 11.47 .
Joma, totally loving this type of videos. I would pay to learn like this xD
pay 900 dollars ?
I came here cause the hashmap solution failed and my whole world went upside down 😥
Thanks Joma, I'll have to revisit this video again to grasp it completely but I tested out your code from repl and it worked really well. Coming from a non-math background my tests showed that the below simple code is only 2-3 times slower than floyd's algorithm for large arrays (10k items - 0.00015s vs. 0.00033s) and not orders of magnitude slower like when creating a set or sorting the initial array.
nums = [1,3,4,2,2]
for num in nums:
if nums.count(num) > 1:
print("Duplicate value is =", num)
break
Great video. This is my favorite anime.
At 14:35 "you can just think about it" is, well...unenlightening
The proof is under the assumption that y > 0
if y = 0, then xmodL = 0, meaning x is a multiple of L, which implies the meeting point would be at the start of cycle, and the tortoise would still meet the new pointer at the start of cycle, so in the end everything still works out
"bunch of mods and stuff like that" Take that, @Neetcode!
oh Joma your video is so awsome T^T
"Senpai you are so cool!!"
RIP , was searching for floyd warshall watched the whole thing :))
Damn!! Now I may want to check out your other videos
yo this is dope homie, nice work
Explaining programming with anime its the best thing i have seen after ben10
big need, thanks joma
Beautifully explained. Thanks.
I'm not even a programmer but I need to watch this. Since the Anime was just to good.
iKnowRealTV lol, best answer. How did you get into programming? Umm, I watched anime. Lolz
@@merowareinstance facts
Thank you very much!! I just started studying C, like, 4 hours ago, and got pretty happy to kinda understand the anime video an fully understand this one! Subscribed!
Hey man love your videos! Someone with programming, tech, and comedy lol
You should have explained how we know we will start on the line part of the graph: 0 indexed arrays, but numbers start at 1.
Yeah I was also confused on that part.
This would make way more sense if you just used actual numbers and physically showed the pointers moving. Then you could explain how the algorithm works in abstract with all sets of numbers following this rule set. The way it is now just begs more questions than it answers, and the model/visual aid becomes misleading. For people who are already half way there, it works. For everyone else it's just confusing.
I found this algorithm way before for finding out if a Linked List has a cycle. So I was surprised when I saw this same algo used on finding a duplicate number in an array.
I was surprised as well. ~Turns out it doesn't work. Try [1,2,2] or [2,1,3,3]. See my comment for why.~ EDIT: I WAS WRONG! IT WORKS AFTER ALL 😮
@@zAlbee2 please explain why it works on [2,1,3,3] my brain tells me it would be stuck on number 1 (index 1) and think it's the solution.
UPD: ok so the reason why [2,1,3,3] would still work is because we start from index 0 and jump directly to index 2, which contains value 3. this fixes both turtle and hare on index 3.
holy shit this came to me. if a number is pointing to its own position it's basically out of the graph completely unless it's duplicate! genius! thank you Albert for giving a push in the right direction now I see the solution clearly AND understand why it works
Stumbled upon the channel because of anime video, like it so much so that look for this video for the explanation :D subscribed for the normal educational content
For the input set [2,1,4,3,4]
The 2 and the 1 point to eachother, and the 4 and 3 also point to eachother. How does the algorithm deal with the case when the duplicate number is entirely outside of the loop that starts with index 0 ?
@18:36 L-Y is not the remainder of Y mod L after all the other Ls are gone. Rather we know that there is at least one complete loop by hare before it meets tortoise, so we rewrite (k*L - Y) mod L as (L - Y) mod L (since k cannot be zero) which is Z mod L which equals Z.
One flaw is that the turtle can travel multiple l, just like the rabbit, instead you use x+y. But basically, the whole idea is absolutely true! Nice one!
Nice proof, thanks a lot, man!
Use a Tardis instead of a Tortoise, so that P = NP.
the best video for explaining why the distance magic would work! X mod L = Z is amaing!
Here he told the hare runs twice as fast as tortoise
But how does it explain
Tortoise = nums[tortise]
Hare = nums[nums[hare]]
It doesn’t make sense how its twice as fast
It just goes at the value of the index as a index
Tortoise = nums[tortoise]
(I say node, but I just mean the position in the array.)
The tortoise is a pointer to a node with an index and a value. The value is the index of the next node that it moves to. If tortoise is at a node with an index 0 and value of 2 (first element of array has index 0, it happens to have the value 2), then the tortoise pointer moves to the node with an index of 2 and some other value .
Hare = nums[nums[hare]]
The nums[hare] part is equal to the node with an index of what hare was before this statement and some value that’s the index of the next node (following the same logic as the turtoise). So now hare = nums[value of next node] will bring the hare’s pointer to the next-next node (compared to where it began)... yeah, you can tell I’m not good at explaining, but I hope this helps!
Jacky Chen Thanks
I can understand that
But my Question was how does it make it 2 times faster
I thought it will b something like if the index is 2 then the next pointer will index 4 since it’s times 2
I can understand the logic of how it’s going
But in the video he told it 2 times faster so I got confused of how exactly it’s 2
Where as it’s clearly not a multiple of 2
Thanks for the effort of explaining
So you can imagine nums[var] as getting the destination of the next step from the position var. Now, since we want to the hare to move twice, we could(alternatively) code it like this:
1step = nums[orgpos]
2step=nums[1step]
However note that we can simply use substitution to simplify the code as
2step=nums[nums[orgpos]]
appreciate for this detailed explained video!
I proved this around the other way.
First I started by modelling the distance the tortoise and hare are from the start at any point.
Let k be the number of iterations that have occurred, d be the diameter of the cycle and i be the initial distance before the cycle (including the start of the cycle)
let n1 be the number of times the tortoise has gone through the cycle and n2 be the number of times the hare has gone through the cycle.
As the tortoise's distance increases by 1 each iteration and decreases by d every time it loops, it's distance will be k - n_1d.
As the hare's distance increases by 2 every time and decreases by d every time it loops, it's distance will be 2k - n_2d.
When the overlap, that means that T = H (where T = tortoise distance, H = hare distance).
Therefore, at this point, k - n1d = 2_k - n_2d. Rearranging this, we find 2k - k = d(n_1 - n_2) or k = d(n_1 - n_2)
Consider now k mod d. As n_1, n_2 are integers, and k = d(n_1 - n_2), k is a multiple of d, and thus k is congruent with 0 mod d.
Our goal is to find the point at the beginning of the cycle as that's the point with in-degree 2 or more. (by definition, this will occur after a distance i as defined above)
In this loop, we perform i iterations to reach our goal. this means the tortoise would have moved i times.
This means the new tortoise position will be equal to T_i + i where T_i is the initial position of the tortoise.
As T_i is congruent with 0 mod d, t_i + i is congruent with i mod d.
As each point on the cycle is congruent with 1 distance mod d, two distances being congruent on the cycle implies they are at the same point, and thus the tortoise must be at the goal.
18:36 For the people like me who didn't understand this explanations, The reason why ( L + L + L ... - y ) modL equals "L - y", not equals to "- y " is if there's some subtraction operator in modular, we add one more mod value to avoid negative result. so... (k * L - y ) mod L is ( (k * L) mod L - y modL + L ) mod L. so.. like ( ( 10 * 3 ) - 4 ) % 3 is not equal -1, but 2. Thanks to this video, I finally realize why should I learn discrete mathematics..
I still don’t get how we use it for the problem in question though 😅
Me too mate
*Turtle and rabbit algorithm*
Floyd: nah
*Tortoise and hare algorithm*
Floyd: Now we're talking
The confusion for me was that the array isn't an arbitrary array of numbers. It's actually a linked list that can potentially go into a infinite cycle.
Please make more anime videos. It makes programming so funny and enjoy to learnt 😁
what is funny here is how everyone complains about hacking in movies but even when actual engineers write a story about hacking or programming they describe steps completely wrong for cinematic purposes
Just use set negative to the value index and use the abs of the value while you scan the array to check whether the value index is negative. If its negative it means it has duplication.
Err what are you talking about?
Yeah I saw that solution, but in this case you can’t modify the array
I just have to take a NOTE of how killed L in 12:53
Just according to keikaku
13:12 If you have dry throat, then why do you want to sing? Crazy Joma 🤣🤣
WAIT, THIS AREN'T MOORE AND MELEY like algorithms?! WAAAAAIT, THOSE ARE "JUST" some types of CYCLE DETECTION ALGORITHMS?!
MIND BLOW
i still don't get it,. maybe after code by my self or read some explaination from other reference,. my brain too hard to understand..
Seeing “too slow bitch” next to the big O notations was too much for me
n = int(input())
duplicate = 0
for i in range(1, n+1):
duplicate = duplicate - int(input()) + i
print('duplicate: ' + str(n - duplicate))
This works !
Time is O(n)
Space is O(1)
Verithanam da Mamey!
yes macha
I am not a programmer but I felt the need to understand
Ahaha nice, was actually going my own research on it, now I get this recommendation
me too
why does the tortoise reach the meeting point without making any full cycle
That is so cool! What program are you using for this video?
Someone PLZZ proove that first time tortoise and hare will meet will not take more then 1 round of loop by tortoise.
I thought that the opposite of division was multiplications...
I almost commented on the equation but then I realised you were correct it's just the way you described it confused me. Anyways, well done, I really enjoy reading on mathematical algorithms and this one was really nice, I enjoyed watching the vid. I really enjoy the mathematical aspect of programming it's quite fascinating how mathematics is everywhere in our lives. Proves how idiotic it is to think mathematics is useless after school. Well, loved the vid.
Try the binary counting search.
start with min=0 and max=n
while (max>min+1){
mid=(min+max)/2
g=count(min
Donald Hobson input not sorted
(k*L) mod L = 0, but you put L above there
So, I think there should be a correction.
x mod L = (k*L - y) mod L = (0 - y mod L) = -(L-z) mod L = z mod L = z (z < L)
Hence, x mod L = z
WDYT?
so basically..
2(x+y)= (x+y+z) +y //left part for tort...right for hare (total dist covered till now)
-> x =z
yayyy!!
So its explained why the tortoise will not go over a loop before hare cacthes him?
It is not necessary to guarantee that the distance travelled by the turtle is gonna be x + y,
except to prove that the algorithm is gonna take at most n steps to finish.
If the turtle's distance was x + y + q*L(where q is the total loops the turtle does)
then Hare distance = 2(x+y+qL)
then 2(x+y) + 2qL = x + y + kL (k total loops the hare does)
x = kL - 2qL - y
x mod L = (L(k-2q) -y) mod L
also k >= 2q since the hare can't do less loops than twice the loops the turtle does
Then, x mod L = L - y mod L
and so x mod L = z
I came for an explanation but left at 4 minute mark because I felt more confused than before.
This video is pure gold
U can get in a way like... There is a circular race track... Everyone starts with different speed.... They will meet again at there LCM of speed... Trying in linked list loop
no you cant like that because you have to first know where the circular track starts.
beautiful explanation
What if the induced graph has multiple connected components (a.e. [2,3,1,5,6,5,5])? Starting in a wrong connected component means that you won't get a correct result, right? Am I missing something? Is this input illegal?
So, once we get X mod L means Z we have the starting point of the circle and decreasing by 1 we have the duplicate number, right? If I am right, then why don't we say the meeting point is the duplicate number? In the problem they didn't want positions of duplicate numbers. The just wanted the value which was written twice. Ain't that right? or we just need to make sure that duplicate numbers exist and we need to check arr[x-1]==arr[x+z]?
tor-tus - tor, like door, then tus, like fuss.
For some reason this makes me think of the movie tenet.
Xor operation is also a way to get single dublicate value.
Another episode of; shit you don't use in real life but they ask you about in interviews.
If someone understood can he please explain me how does this help to find a duplicate Number?
Thx
Yeah, so think about the indices from 0 to n being the nodes (the array has length n + 1). At each index/node, think of the value contained in the array as being the arrow into the next index/node. So the index in the array tells us the node, and the value at that index tells us the next index/node. Since there is a duplicate number in the array, two distinct nodes/indices in the array will point to the same index in the array. Our goal is to find the node that is pointed into by two different nodes.
Now how do we find the node that is pointed into by two different nodes? Well, since we know that every value is between 1 and n, we know that the node at index 0 will point to an index/node within the range 1 to n in the array. We also know that once you get into the 1 to n range of the array, every next element will be within that range as well. Because of this, we know that if we start at node 0 and move forward, we will immediately reach the 1 to n range, and then once we're there, every node will point to some node within the same range, so we must have a cycle in that range.
So we know that node 0 is not part of the cycle (since no node points into it due to the fact that all nodes point to nodes that are in the 1 to n range), but we also know that following node 0 will eventually lead us into the cycle. Because we can guarantee that we start without already being in the cycle, the node that starts the cycle will be pointed into by two different nodes (the node right before the cycle, and the last node in the cycle). But this is precisely what the goal I stated in the first paragraph was. So this entire algorithm is just to help us find the node that represents the start of the cycle, which must be pointed into by two different nodes/indices in the array, and hence must be the value that is duplicated.
@@Theactualstoic Wow, I'm so happy to hear that! I thought no one was going to read my answer, so I was just writing to solidify my understanding, but I'm so happy it was useful to you :D
Dude new channel 😎👍👍👍👍👍
Interesting, I have no idea about what I am doing right now.
Can somebody please explain how to find out the length of x and thus the start of the loop? Everything afterwards is clear to me
An explanation about finding the entry point part.
First assume when fast and slow meet, slow has moved a steps, and fast has moved 2a steps. They meet in the circle, so the difference a must be a multiple of the length of the circle.
Next assume the distance between beginning to the entry point is x, then we know that the slow has traveled in the circle for a-x steps.
How do we find the entry point? Just let slow move for another x steps, then slow will have moved a steps in the circle, which is a multiple of length of the circle.
So we start another pointer at the beginning and let slow move with it. Remember x is the distance between beginning to the entry point, after x steps, both pointer will meet at the entry of circle.
Hey Joma, what tablet do you use to do these types of explanations? Really need a simple and clean one. Thanks
6:03 Why do you use a set and not another array/list? You’re gonna fill n elements in the worst case scenario in both so is there an advantage in using a set?
n(n+1) divided by 2 wouldn't actually works also if the n is really big and the sum will simply overflowed
I tried it and it did not work. Then I realized the ints start at 1 not 0, and it worked.
I tested, it works but I didn't understand just why it does work. Thing I didn't understand is neither tortoise nor hare is following a regular sequence. For example in that anime video, code is used for 3,1,3,4,2 array if I am not wrong. In that example, tortoise goes from first element of array to fourth element of array then fifth element of array then thirth because the code is tortoise=nums[tortoise] and hare goes from first to fifth to fourth to thirth because the code is hare=nums[nums[hare]]. Tortoise doesn't go like 1 forward 1 forward 1 forward. It goes 3 forward 1 forward 2 back. I understood the math in these video and why x mod L = z but what exactly prooves x mod L = z and why? Can anyone help?
Hey Joma, I think creating a new channel about Algorithm was the right decision, I feel the Joma Tech channel is goingdown in many aspects, good luck to you !
Make more videos about algorithms or data structures....
What will happen if, let's say, there is a value of 1 in an element with the index of 1?
array must be zero indexed, so at firs you must reach some index with value 1 to reach index 1, this means the duplicate number is 1, otherwise you can't reach index 1. it's not special case.