Euclid Algorithm Coding

A free video tutorial from Tim Buchalka's Learn Programming Academy
Professional Programmers and Teachers - 2M students
Rating: 4.5 out of 5Instructor rating
59 courses
2,020,484 students
Euclid Algorithm Coding

Lecture description

In this video we will implement the euclid algorithm. We will also implement the recursion and non recursion version of it.

Learn more from the full course

Advanced Algorithms in Java

Understand Algorithms and Data structure at a deep level. Grow your career and be ready to answer interview questions!

16:13:28 of on-demand video • Updated November 2023

Have an understand of how algorithms work, at a deep level
Write better Java code that is more optimised
In this video, we are going to code our Euclid algorithm. So to start with that, let's go to search main java. Let's create a new packaging here, which will be called academy .learnprogramming.algorithm.euclid, okay. So you should see something like this. Now let's create a new class, which we don't need to invent any crazy name. Let's just call Euclid. And let's add some comment here saying Euclid algorithm and Euclid. It will calculate or actually it calculates the greatest common divisor between 2 numbers, a and b., so it's a greater common divisor between a and b. All right. So first implementation we are going to make is an implementation using recursion. So let's create a public int greater common divisor, like just gcd. And let's say int number and divisor. Okay. And what we do here, remember, we had -- let's add a little comment here so we can follow the same situation we had in our introduction. Implementation using recursion. And let's break line here. And here, I'm going to say we had 22 and 6, which was 3 and rest of 4. Then we had 6 and 4, got 6 from here, 4 from there. And the result of this is 1 rest of 2. And then we had four and 2, which was 2 rest of 0. So let's implement that and talk to this as we implement. First thing we need to do is get this number. So we have these 2 numbers here and here. We need to divide them and get the rest. So let's call remaining equals and we can just say number. Let's use this module divisor. This is going to give us number 4. We will assign number 4 to the remaining or 0. or 0. But in this case here 22 and 6 would be 4. So what we need to do is let's create an if condition here and say if my remaining is not equal 0, I will call it again. So I will do return grade common divisor, but what I'm going to send back is, remember, I need to send the divisor as a number. So I'm going to send here divisor. And now my number is actually my remaining, my divisor is actually my remaining, so remaining. Okay. Call it again sending divisor and remaining, and it's going to cause many times as it takes to reach 0. When it reaches 0, we are going to return the divisor. So remember, when it reaches 0, the divisor is our common greatest common divisor between those 2 numbers. And that's it. This is the implementation. But let's suppose that you are in an interview or I don't know you need to implement this some other way. So let's implement, have the same implementation but not using recursion. Let's say public int, great common advisor. Let's call create common divisor 2 and int number and divisor. Okay. And the difference now is what I need to do is create a loop. This 1 didn't need the loop because it keeps calling again and again and again. And in this case, I actually need a while loop. And I'm going to do while this happens, remaining, which in my case I'm not going to keep creating variables, I'm going to change the divisor. Divisor is not equal 0. There are many ways to implement this. This is the way I'm implementing here just to illustrate. But if you find another way, feel free to do it. Just create unit tests and be sure that it's working properly. So what I'm going to do is I'm going to create a temp variable. Let me show you what I'm going to do here. So implementation without recursion, and we're going to use the same example. We add in here. And so basically what I'm going to do is we have the number. So this is the number divided by -- there are 2 stages here, one is this is the divisor and also divisor or temp or it's actually the divisor and the temp and equals result of rest of and this rest of would be -- we'll get there, would be actually the divisor. So this will become the divisor. So let's do like this to make life simpler. This is what we are going to have after I start modifying. Let me show you what I mean with that. I'm going to start create a temporary variable and say hey, my divisor is my temp now. So whatever I have here became my temp. And what I need to do now is do the calculation. So I'm going to change my divisor. And my divisor will be the module of this calculation. Why because I need to call it again sending the divisor. So I'm just preparing the divisor here to do that already. So I'm going to say number module divisor. Okay. So let's say we have 22 and 6. And here we say yo 6 not equals 0, great got to get in there. Now assign 6 to my temp variable. Great. Now change my divisor from 6, it will become 4. So my divisor now is 4. So the only thing I need to do is change my number to 6, which is my temp. What I'm going to do number equals temp. And that's it. And that's it. So let's run one more thing. Actually in this case, I'm going to return the number. So let's run through this example and see if it's actually going to work. First thing we get is 22 and 6. So I assign 6 to my temp variable and I say hey whatever I had on my divisor now has 4 in it which is the result of that division. So my divisor became 4 which was 6, so I'm preparing for this line already and my number became whatever I had on my divisor, which was 6. So I have 6 divided by 4. When the loop goes to the next round, it says all right what do you have on your divisor, I have 4 because I change it here. Okay. Put four in the temporary, and let's divide it again. So let's divide 6 by 4, the rest will be 2. So my divisor now will be 2 and my number will be 4. Another round now I'm here and assign my divisor to temp which is 2 divide, the thing and it's going to get 0 on the divisor and say now my number is actually my temp, which was 2. So that's why we return number because we have that, we assign temp to that, which was our divisor. And divisor will be 0, gets out of there, returns the number which is 2. The greatest common divisor is 2. So this is how it works. If you didn't understand, just come back to this lecture. It's very short lecture. And if you did, let's go to the next video where we are going to unit test it.