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

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

[@camuongphan6286]

When a joking video had a good content

[@PflanzenChirurg]

this is legendary

[@Rhidayah]

Senpai why you so fools 🤣 Just kidding

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

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

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

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

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

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

[@pinoyXasian]

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

[@TheSchwartzable]

This was exactly the explanation I was looking for!

[@abhilashpatel3036]

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

[@tseren]

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

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

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

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

[@Iknowrealtv]

I'm not even a programmer but I need to watch this. Since the Anime was just to good.

[@merowareinstance]

iKnowRealTV lol, best answer. How did you get into programming? Umm, I watched anime. Lolz

[@Iknowrealtv]

@@merowareinstance facts

[@ImposterBraum]

Oh my god thank you soooo much Quality work as usual

[@PflanzenChirurg]

MORE ALGORYTHMS PLEASE! This was astounish entertaining

[@TrueZenquiorra]

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

[@edwingarcia5043]

pay 900 dollars ?

[@BetaNegative]

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

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

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

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

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

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

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

[@c0dertang]

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

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

[@imacds]

Use a Tardis instead of a Tortoise, so that P = NP.

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

[@효정씨-e9c]

"Senpai you are so cool!!"

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

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

[@vinaysinghjadon1959]

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

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

[@hunghung-mu6se]

thanks you for Floyd's Algorithm Explained

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

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

[@dark_knight987]

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

[@k2x2x2s]

oh Joma your video is so awsome T^T

[@akxyn5010]

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

[@forgottenmohawks8734]

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

[@henkkk450]

Me too mate

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

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

[@Saronite]

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

[@codeinnovator]

n = int(input()) duplicate = 0 for i in range(1, n+1): duplicate = duplicate - int(input()) + i print('duplicate: ' + str(n - duplicate)) This works !

[@codeinnovator]

Time is O(n) Space is O(1)

[@Zafoshin]

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

[@fanskucing597]

Just according to keikaku

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

[@siddhantdeshmukh7120]

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

[@Avalanchanime]

WAIT, THIS AREN'T MOORE AND MELEY like algorithms?! WAAAAAIT, THOSE ARE "JUST" some types of CYCLE DETECTION ALGORITHMS?! MIND BLOW

[@SauravKumar-kj1uu]

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

[@bansalashu1613]

no you cant like that because you have to first know where the circular track starts.

[@garrett-o5l]

Great video. This is my favorite anime.

[@Eireannade]

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.

[@lamrin9178]

RIP , was searching for floyd warshall watched the whole thing :))

[@203bigd]

yo this is dope homie, nice work

[@kongzilla2897]

so basically.. 2(x+y)= (x+y+z) +y //left part for tort...right for hare (total dist covered till now) -> x =z yayyy!!

[@bagasadifirdaus9278]

So its explained why the tortoise will not go over a loop before hare cacthes him?

[@ClaudioParraGonzalez]

Beautifully explained. Thanks.

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

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

[@muchammadwahyu2993]

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

[@artemy1046]

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

[@seekndstroy2560]

big need, thanks joma

[@yuhaokong]

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

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

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

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

[@jasonhsieh8644]

the best video for explaining why the distance magic would work! X mod L = Z is amaing!

[@Arjunsiva]

Verithanam da Mamey!

[@sanjayd9675]

yes macha

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

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

[@xx_Ashura_xx]

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

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

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

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

[@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 ;)

[@LittleWhole]

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

[@k0alk0]

What will happen if, let's say, there is a value of 1 in an element with the index of 1?

[@nikatamliani3790]

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.

[@iamtrash288]

Because of the whole anime theme I always cracked up when he said L. I was like, I know he means length but damn, man it's just too anime

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

[@huuphuocle2633]

Correct me if I'm wrong. But if you start a a node in the circle, the two pointers will meet at the starting node, them you will return value of that node no matter where the duplicate is. Edit: i figure it out.

[@Glement]

How does cycle finding algorithm helps you find duplicates?

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

[@donaldhobson8873]

Try the binary counting search. start with min=0 and max=n while (max>min+1){ mid=(min+max)/2 g=count(min

[@neogovn]

Donald Hobson input not sorted

[@sanjary]

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

[@amazeng1111]

Modular arithmetic ： a≡b(mod m) can simply prove it

[@TraceguyRune]

But what is the line vs the circle?

[@vaibhavattre3542]

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

[@lmeza1983]

I came for an explanation but left at 4 minute mark because I felt more confused than before.

[@ichione732]

This is already explained in the LNs, but pretty helpful for anime onlys

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

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

[@NivedhaOrton]

Make more videos about algorithms or data structures....

[@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 )?

[@z41n]

Hey Joma, what tablet do you use to do these types of explanations? Really need a simple and clean one. Thanks

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