If yall had read the manga yall wouldnt need this explication

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

When a joking video had a good content

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

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

yutube overestimated my intelligence once again by recomending this one

Thank you, Senpai!

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.

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

Oh my god thank you soooo much Quality work as usual

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!

This was exactly the explanation I was looking for!

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!

yo this is dope homie, nice work

big need, thanks joma

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

MORE ALGORYTHMS PLEASE! This was astounish entertaining

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

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

oh Joma your video is so awsome T^T

Great video. This is my favorite anime.

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

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

appreciate for this detailed explained video!

Beautifully explained. Thanks.

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

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

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

thanks you for Floyd's Algorithm Explained

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

Nice proof, thanks a lot, man!

This video is pure gold

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

beautiful explanation

Dude new channel 😎👍👍👍👍👍

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

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.

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

Excelente! I admire you!

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 ?

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

Cool joma has a programming channel thank you joma

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

thank u so muchhhh

Question, how you avoid lenght 1 loops in the question in the original video? like if 1 is the first element?

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

Coolness Intensified

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

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

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

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.

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.

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?

Can't wait for the season 2

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?

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.

Verithanam da Mamey!

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

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.

Thanks

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

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.

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

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

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

But what is the line vs the circle?

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

where do i start to learn most of this? any books you can recommend?

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?

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

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?

"Senpai you are so cool!!"

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

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?

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

hey man, nice videos. (im not good at algorithms and stuff)Just wondering, would you be able to determine (from the limitation in speed) how long can the variable N get? Cuz then, by seeing the time in which the program has to determine the duplicate, you'd know that even with an algorithm like Floyd, if you have N a certain size it would exceed the time.. So you could just estimate the max length of N and just make a frequency array... I m not sure if this would really exceed the space no matter what, but time should be fine.... right? probably its really stupid question, the main thing is that a frequency array wouldnt work cuz the max size of N is not specified, and im really trying to see if theres a way to make it work.

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!

How do you get from an array to a graph using pointers?

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

great explaination, you could have explained how to write code for it too,

hello senpai, ware ware wa Pain.. kami da, and my question is what is the name of program you use to write things out on screen. Thank you so much

Anyone know what software he uses for the explanation (blackboard)

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

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

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

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

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.

What program/app are you using for the drawing here? It's really nice and clean!

Hey Joma San tell me, How to start practicing these algorithms, and what is the best resources / websites to do so?

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.

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?

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.

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

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

You thought this video is supposed to be meme, but it was ME FLOYD!

In your anime, you find a duplicate number using the value at a given index as the next index. Is there a generic solution for the special case where a[0] := 0?

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

senpai，you are so smart

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

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.