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:

1. 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
2. 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
3. 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

1. use for loop and identify opportunity to break the loop earlier (this is my choice)
2. use recursion but we need to know Euclidean Algorithm first
3. 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