Programming Anime: Floyd's Algorithm Explained

[@project-pe6ly]

If yall had read the manga yall wouldnt need this explication

[@JomaClass]

Lmaoooo

[@The9TKitsune]

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.

[@randompotato26]

TBH I think some details are still missing... the LN was a lot nicer and I would recommend over the manga for sure.

[@prodigg9299]

Best comment I've read in a while lmaoo

[@martinochristanto5216]

if you read the light novel you could be the senpai teaching him this algorithm

[@nintorws]

1.4 million people: Watch a programming anime video just for fun. 36804 of them: I need that power!

[@anupchandrahangrai1217]

Glad to be one of the 95,899.

[@mechatronicsprojectsandsim8337]

Glad to be one of them

[@mrdarip4289]

Glad of be one

[@Bluesourboy]

Glad

[@cp0bo593]

Gla

[@camuongphan6286]

When a joking video had a good content

[@PflanzenChirurg]

this is legendary

[@Rhidayah]

Senpai why you so fools 🤣 Just kidding

[@abigailyang39]

Was just randomly watching funny videos to relax. And now I’m here studying during my break time

[@arpitkumar4525]

Lol same

[@juanandrescastillofuenmayo6619]

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

[@doubleliu]

Its 4 am trying to sleep

[@romyojitpaul2200]

same bro 😂

[@alg_strawhat129]

I wanted to program it myself but I couldn’t, because of my carpal tunnel! Kuso!!!!

[@moodman6426]

unlucky

[@Seba-le7mb]

If you had read the manga, you could be able to do it.

[@abeeonaboat1741]

Try use voice to text

[@MsJooy]

yutube overestimated my intelligence once again by recomending this one

[@_cytosine]

Bro, you got this.

[@merowareinstance]

Lol, you can do this. KZbin algorithm will provide what it knows you can handle 😄

[@NStripleseven]

H

[@kienhuynh1614]

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.

[@knightartorias5872]

This is 4 months old but thx man

[@FINSuojeluskunta]

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.

[@yelena_]

Thank you. This comment is what got me to finally understand it.

[@snooglemunch]

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?

[@yelena_]

​@@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)

[@princyangelina_n]

Thank you, Senpai!

[@defalt7732]

Your comment made him to do this vid🤣 Tq

[@princyangelina_n]

@@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.

[@Majestic469]

Lol

[@darthbumblebee7310]

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!

[@misterplus306]

Thank you so much man! That video appeared in my recommendation yesterday and I was so confused... This video is much easier to understand.

[@dimylameri]

Can you imagine another application for this algorithm? Because it seems pretty specific to this problem and these constraints

[@JomaClass]

Not gonna lie, it’s pretty useless in real world applications.

[@kratosgodofwar777]

@@JomaClass bruh

[@Fenvirr]

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.

[@TheNewton]

Embedded hardware, SKU handling

[@tdgray978]

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.

[@mohammednagdy6661]

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!

[@hilmidwiputranto6944]

1:17 he even gave a spoiler warning, such a cultured man

[@ImposterBraum]

Oh my god thank you soooo much Quality work as usual

[@Benw8888]

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

[@rct3vids99]

Thank you for mentioning this! I was wondering about the 0th index and this makes perfect sense

[@Timformers]

When a comment blows your mind way more than the video

[@L1Q]

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

[@samuraijosh1595]

@@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.

[@omerozkaya2856]

​@@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!

[@TheSchwartzable]

This was exactly the explanation I was looking for!

[@jrmh_hs]

oh Joma your video is so awsome T^T

[@kevinstefan98]

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.

[@yogiturtleseraph8208]

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.

[@_Ytreza_]

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.

[@pinoyXasian]

bruh, this is helping me study and is making it the first leetcode medium I've solved. Whoever said anime wasn't useful?

[@MehtaAvant]

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 ?

[@203bigd]

yo this is dope homie, nice work

[@dark_knight987]

Belive i was just left wondering watching the anime video ,keep up these algorithm videos ❤

[@TrueZenquiorra]

Joma, totally loving this type of videos. I would pay to learn like this xD

[@edwingarcia5043]

pay 900 dollars ?

[@Rohith_E]

@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.

[@del6553]

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

[@pablojavier7965]

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?

[@PflanzenChirurg]

MORE ALGORYTHMS PLEASE! This was astounish entertaining

[@tseren]

I watched a few of these and didn't grasp it until I watched your mathematical explanation. Thanks.

[@siddhantdeshmukh7120]

Damn!! Now I may want to check out your other videos

[@kr13031]

Thanks sir, this helped me last night to sleep after 2 days of no sleep. After I checked I fell asleep at 11.47 .

[@AleksandarDragon]

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

[@xx_Ashura_xx]

Hey man love your videos! Someone with programming, tech, and comedy lol

[@garrett-o5l]

Great video. This is my favorite anime.

[@blindarion4127]

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?

[@GalaxiaDeFavio]

15:40 in the video why the hare distance doesn't have the z?

[@henkkk450]

If someone understood can he please explain me how does this help to find a duplicate Number? Thx

[@GodisgudAQW]

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.

[@GodisgudAQW]

@@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

[@BetaNegative]

At 14:35 "you can just think about it" is, well...unenlightening

[@miggs8075]

18:23 shouldn't the leftover be just -y? I mean the mod is going to get rid of all the L's therefore the only reminder is the -y.

[@bryany3241]

The doesn't get rid of all the L's. In math, the modulo cannot return a negative number (in programming languages tho some languages let u return a negative number).

[@forgottenmohawks8734]

I still don’t get how we use it for the problem in question though 😅

[@henkkk450]

Me too mate

[@naasifn]

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]?

[@abhilashpatel3036]

I came here cause the hashmap solution failed and my whole world went upside down 😥

[@Seanabo]

I get that we've found a cycle but I still don't get how that cycle is used to find the duplicate number in given set.

[@RioChandra]

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..

[@flow5718]

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

[@효정씨-e9c]

"Senpai you are so cool!!"

[@rajaelhajj6989]

why does the tortoise reach the meeting point without making any full cycle

[@bobysayslbobysays6006]

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.

[@emmaodonnell8275]

Can you get a false positive on a cycle here? If you're using 1 based indexing and you start the hare and turtle in position 1 then you immediately get stuck in a loop right?

[@not_vinkami]

so why don't we use nums.count(i) for i in nums (Not in correct syntax)? We can just catch nums.count(i) > 1 and output i

[@vm20709]

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.

[@RainerRitsch]

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

[@siobhanahbois]

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.

[@cp0bo593]

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?

[@groovyoxygen1805]

What about [2, 1, 3, 3]? Wouldn‘t both pointers just get stuck in the first loop and never reach the 3s?

[@Swedishnbkongu]

Exactly my thoughts, it's essentially like unconnected regions of a graph

[@Swedishnbkongu]

Nevermind, since the array is 0-indexed as usual, and the problem said all the numbers are from 1 to n, no value will point to index zero (no value can be zero), so it cannot be part of a cycle. It then follows that any cycle in the array is after index zero, and that the structure Joma showed in the video is correct, with a noncyclical tail leading into some cycle, and meaning a duplicate is present if and only if there is such a cycle

[@B1SQ1T]

I'm a bit confused by the whole traverse then loop part. Is X the size of the whole array? Like say I have [1,2,3,4,4] is X gonna be 5?

[@Ne3zyTV]

but I don't understand how random duplicates in an array is a cycle ????? how is this [4,3,4,4,6,5,1] a cycle ???

[@krismacstadium6658]

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

[@hunghung-mu6se]

thanks you for Floyd's Algorithm Explained

[@callmechocolateboy]

Dude new channel 😎👍👍👍👍👍

[@Ureallydontknow]

But you didn't show the function calls or the instruction set with pointers. I already know modular arithmetic and coding but I'm not sure what this video can do for me. Show the code.

[@couchcamoteChannel]

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]

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 😮

[@L1Q]

@@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

[@Glement]

How does cycle finding algorithm helps you find duplicates?

[@funnygeeks8126]

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.

[@EricDongh2p]

Yeah I was also confused on that part.

[@kaldrass8252]

Sorry I think I didn't understand it well as i'm not that good in english, but one question remains for me : If you want to make the algorithm, you have to make the hare do the cycle, but it means you already know at what node the cycle begins right ? So I don't understand how to make it without already knowing the location of the beginning of the cycle... please enlight me ! edit : And why knowing that would help us knowing which number is duplicated ?

[@Kris_misra]

Hey can we also use it in counting how many times that particular alphabet is being repeated I a string(array of string )?

[@ok_7566]

Hey will this not work TOO here if I go through the array at once take the max and sum of array. int sum= "sum of array" int max ="maximum no in array" int N = "no of elements in array" Now I can do sum-(max*(max+1))/2/(N-(max+1)) I have the element that is repeated.

[@YosefTukachinsky]

Look like this algorithm should work only if the starting point guarantee to be outside the loop. If the starting point is already inside the loop - the meeting point will always be the starting point, no meter where is the tail. do I miss something?

[@ramstube08]

What I don't understand at starting is, why there is loop at the end of a line? How does it form? I'm sorry if I sound dumb... Without that I'm not able to concentrate on the rest of the video....

[@Zafoshin]

I just have to take a NOTE of how killed L in 12:53

[@fanskucing597]

Just according to keikaku

[@helboy1111]

Am I correct in my understanding that after the hare moves 1 by 1 (from the meeting point described at 8:08 ), the hare might still loop any number of times before getting to the start of the loop at the same time as the turtoise? Since the turtoise moves x, which is later written as l + l + ... + l + a, and a = z that would mean that the hare still moves any amount of loops equal to the distance the turtoise has to travel as l distance as part of x. Great video! I already put aside the Wikipedia page on it for later, but this works even better ;)

[@richard1762]

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.

[@Naton]

Err what are you talking about?

[@jasonpamintuan7096]

Yeah I saw that solution, but in this case you can’t modify the array

[@TraceguyRune]

But what is the line vs the circle?

[@seekndstroy2560]

big need, thanks joma

[@DrPastah]

7:37 Is he saying Tortoise or Turquoise?

[@LUITEN1]

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!

[@zuochuheng8909]

Hi, I think I still have problem understanding the proving part. The part that proves x mod L= z using M+k*L looks straightforward , I'm just confused about the assumption that make all this work ,hare distance = 2(x+y) , i mean it make sense but not? i know hare is twice fast than the turtle, but it loops in L only right, it dont walk over x ever agian, i just feel 2(x+y) is against my intuition. Appreciate if u can help me think this straight!

[@Sagolel4797]

It doesn't matter "where" hare moves, it just matters how far. Since we know turtle moved x+y, hare has to have moved 2(x+y). The rest is handeled by the mod L.

[@artemy1046]

That is so cool! What program are you using for this video?

[@ClaudioParraGonzalez]

Beautifully explained. Thanks.

[@vinaysinghjadon1959]

Explaining programming with anime its the best thing i have seen after ben10

[@mariodquiroz]

What does stands the "Space" concept for in data structures???? Min 5:20

[@girv98]

amount of memory

[@eui-joonjung5774]

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..

[@danielmc5693]

This might be a dumb question, but how do you know when to end x and start the loop. If the hare went twice as fast as the tortoise, wouldn't if go the beginning of the array?

[@RainerRitsch]

my question exactly

[@randomcarbonaccumulation6478]

From my understanding of the problem, the tortoise and the hare don't go through the array in order (array[0]-->array[1]-->array[2]). Instead, they start at index 0, look up the number in the array at this index, and go there. So if array[0] was 6, the tortoise would go to array[6], and if array[6] was 3, it would go to array[3] in the next step. (The hare does the same, just twice as fast). Think of the value in the array at a certain index as a pointer that tells tortoise and hare where to go next. Because there is a duplicate value in the array, two of these pointers point to the same index. Once the tortoise or hare get to the second occurrence of this value, they go back to a value they have already visited, and if they follow that path, they will eventually get to the second occurrence again and again and again. We don't tell the tortoise and hare where to loop back, they automatically do once they get to the duplicate number. Floyd's algorithm can detect where this loop starts. At least that's what I understood. I hope I could help, tell me if I got something wrong

[@lostmeme9862]

I tried it and it did not work. Then I realized the ints start at 1 not 0, and it worked.

[@antoniamendo]

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

[@jffrysith4365]

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.

[@vaibhavattre3542]

I thought that the opposite of division was multiplications...

[@stellarfirefly]

I understand the math that you explained. But I still don't understand how performing those steps will find you a unique duplicate number in an unsorted array. It seems like the algorithm will always converge on a specific node on a given array depending only upon that array's length. So changing the placement of the values within the array will change the value of the element that you eventually converge upon, i.e. a different solution for [1,2,1,3,4,5,6] versus [2,3,4,5,1,6,1]. How does this algorithm find the duplicate value 1 in both of these arrays? EDIT: Perhaps a better way to ask the question is, when the Hare is traversing the line+loop structure and it finishes its first loop, how do you know where to continue looping if the start of the loop is the very thing you are trying to find?

[@_Ytreza_]

The node that the algorithm fins doesn't depend only on the length of the array. The drawing he made with nodes and loops etc is completely dependent on the values in the array. You start at a[0] In your first example, it's 1, so the next node is a[1] = 2 The next node is therefore a[2] = 1 so you have a loop from here In your second example a[0] = 2 The next node is a[2] = 4 Then a[4] = 1 Then a[1] = 3 Then a[3] = 5 Then a[5] = 6 Then a[6] = 1 and you loop from there I hope you understand better how it works now

[@stellarfirefly]

@@_Ytreza_ Yes, that makes much more sense, thank you. The video's diagram makes it seem like it simply traverses the array in index order. Does the tortoise take single such jumps while the hare takes two such jumps at a time?

[@_Ytreza_]

@@stellarfirefly Yes exactly

[@NStripleseven]

Not sure I understand what Floyd's algorithm does. What is the thing the pointers are on? What does that represent?

[@L1Q]

what happens if any number is pointing on itself? UPD: my mind just ascended to solution. if any number points at itself (value = 0 based index), we will never find it by going from index 0 and forward through the graph. it is only possible to get on the index the value points to by having a duplicate value pointing to same index.

[@kennedyfrancis5875]

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

[@jk-2053]

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!

[@kennedyfrancis5875]

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

[@guythat29]

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]]

[@mengxiaowang7351]

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!

[@chessnotchekrs]

What if the index and value is the same? Index | Value 1 ----> 1 Wouldn't then both the hare and the rabbit be stuck in an infinite cycle? Or if you have a pair of self-referential index-values, like this Index | Value 1 -----> 2 2 ------> 1 You would be stuck. Anybody have any ideas?

[@yuhaokong]

n(n+1) divided by 2 wouldn't actually works also if the n is really big and the sum will simply overflowed

[@c0dertang]

"bunch of mods and stuff like that" Take that, @Neetcode!

[@LittleWhole]

Seeing “too slow bitch” next to the big O notations was too much for me

[@muchammadwahyu2993]

Please make more anime videos. It makes programming so funny and enjoy to learnt 😁

[@Saronite]

*Turtle and rabbit algorithm* Floyd: nah *Tortoise and hare algorithm* Floyd: Now we're talking

[@RomanTokarenko]

Nice proof, thanks a lot, man!

[@nirajraut9408]

Can someone tell me which software he is using to write and proof that algorithm?

[@akxyn5010]

13:12 If you have dry throat, then why do you want to sing? Crazy Joma 🤣🤣

[@sparkx611]

appreciate for this detailed explained video!