# Mathematics — Greatest Common Divisors (Euclidean Algorithm)

## Check out all my other posts in My Technical Articles

# Background

I am participating in weekly contest on LeetCode recently, with a goal to sharpen my skill by picking up those algorithms I yet to know.

# Question of the week

*Link to Leet Code Question** (Number of subarrays with GCD equal to K)*

The question is with a difficulty of medium. It is about finding the maximum number of subarrays in a given array `nums`

with their greatest common divisor of all elements in the subarrays to be `k`

.

# Find the Greatest Common Divisors (GCD)

I could come up with two ways to find GCD between two integers:

**the Common Factor Method**

It is the method I learned when I was in junior high school. It’s very simple. Grab a pen and paper, write down separately all the prime factors of the two given numbers, then determine the common factors. To implement this in programming, I will need to create several functions to do Prime Factorization**Brute Force Loop**

Since we already know the target GCD`k`

, we could use a loop to increment a variable`div`

from`k+1`

to`Math.max(subarrays)`

. If`div`

could divide all numbers in the`subarray`

with zero remainders, it means`k`

is not the GCD for this subarray**Euclidean Algorithm****輾轉相除法**

In mathematics, GCD between two numbers could be found by their remainders, this is called Euclidean Algorithm.*This article*explains very clearly what it is. If you understand it, then it’s not a big deal to come up with a recursive solution

# Possible Solutions

- use
`for loop`

and identify opportunity to break the loop earlier (this is my choice) - use recursion but we need to know
**Euclidean Algorithm**first - use Dynamic Programming to improve recursion performance

# Result

I submitted solution 1 & 2, 3 times for each to calculate the average

- the average runtime performance is around 1600ms
- the average runtime for recursion is around 2500ms (without memoization)
- I haven’t figure out how to use memoization in this case

# Reference

- The codes I wrote, with a very poor runtime ~ 1600ms, could be found on
*LeetCode* - There is another
*recursive version*which is written nicely and has a runtime at around ~200ms