Data Structure And Algorithms In Python — 2

In our last blog, we discussed about basic of Data Structure and Algorithm. We covered basic approach for GCD (Greatest Common Divisor). Today we will cover, other advance level aspects for GCD. We can improve our approach to solve any problem for optimization (find the shortest route to create an algorithm).

Prior to read this blog, I’d strongly recommend to read first Data Structure and Architecture blog.

Though, previously we did compute multiple lists and than compared them to compute common factors cf. However, we can do it in one list only.

1. For each i in 1 to max(m,n), if i divides m and n both, then add i to cf.
2. Any common factor must be less than min(m,n) :
   For each i in 1 to min(m,n), if i divides m and n, then add i to cf

shorter Python program for GCD

In Above mentioned program, we are using List. However, List is also not required. Few points to remember : —

1. We only need the largest common factor.
2. 1 will always be a common factor.
3. Each time we find a larger common factor, discard the previous one.
4. Remember the largest common factor seen so far and return it.

Program Without List

We can Scan our program backwards as well. Points, which we need to follow.

1. To find the largest common factor, start at the end and work backwards.
2. Let i run from min(m,n) to 1.
3. First common factor that we find will be GCD!

In our next blog, we will learn about Euclidean algorithm to compute the greatest common divisor.

Thank you for reading. Links to other blogs: —

Data Structure and Architecture-1
Hessian Matrix
First order and Second order — Calculus
Statistical Inference 2 — Hypothesis Testing
Statistical Inference
Central Limit Theorem — Statistics