Last weekend my wife and I visited our son and family who live in Madison, Wisconsin. They like to cook and bake like we do. When I was growing up, most summer days I would make ice cream. The techniques and ingredients were quite simple.
Over the weekend my son made ice cream. He did it using the ice cream bowl for the Kitchenaid mixer. It happens that we also have an ice cream bowl. When we got back, we decided to make some ice cream using the same recipe that our son had used. We searched for our ice cream bowl which we have not used in years, but were not able to find it. We decided to use a regular bowl and the standard 6-wire whip attachment.
We prepared the ice cream and put it in the freezer. It turned out quite good. 
This next weekend we will modify the recipe and see what comes out. Will let you know our findings.
Let’s now dive into the main subject for this post. I needed to switch tasks for a couple hours so I decided to put a stake at finding the Greatest Common Denominator (GCD) for a set of integers.
When I confront a new task I always like to spend a few minutes looking at what is available on-line. The worse thing is to reinvent the wheel. After selecting an approach, I experiment and test making sure I understand the approach and more important, if the approach solves the problem at hand. In many cases code just needs to be adjusted to your specific requirements.
For this post I went and did a Google search. My choice was based on the Euclidean Algorithm. The idea is to apply it to consecutive integers and use the previous GCD to compare to the next integer in the array.
The code was written in Java. I used the Visual Studio Code IDE from Microsoft on a Windows 10 computer.
When I was done with my code, I wanted to make sure the code did not have hidden issues. The best way is to go to a website that has problems and look for one that is close to your objective. In this case, finding the GCD, I figured that HackerRank or LeetCode would have such problems. To be honest I did not quickly find a problem in LeetCode. I did find GCD of the Array at HackerRank, but it was flagged locked. I decided to skip additional testing.
2 252 105 main <<< n: 2 main <<< arr: [252, 105] main <<< findGCD: 21 main <<< iterativeGCD: 21 main <<< subtractingGCD: 21
The test supports one test case at a time. I was going to change it for HackerRank, but just left it with one case at a time.
The first line holds the number of integers to check for the GCD. The second line contains the actual integers.
The test scaffolding displays the values and makes calls to different functions to compute the GCD. All three approaches return the same value :o)
2 462 1071 main <<< n: 2 main <<< arr: [462, 1071] main <<< findGCD: 21 main <<< iterativeGCD: 21 main <<< subtractingGCD: 21
Like in the previous example, I only tried two values. If not mistaken they are the same examples described in the Wikipedia article. Note that the integers do not have to be in any particular order.
4 1 2 3 4 main <<< n: 4 main <<< arr: [1, 2, 3, 4] main <<< findGCD: 1 main <<< iterativeGCD: 1 main <<< subtractingGCD: 1
In this test case we venture and use four integers. It is easy to determine the answer.
4 2 4 6 8 main <<< n: 4 main <<< arr: [2, 4, 6, 8] main <<< findGCD: 2 main <<< iterativeGCD: 2 main <<< subtractingGCD: 2
The same holds for this example with only three integers.
5 2 4 6 8 16 main <<< n: 5 main <<< arr: [2, 4, 6, 8, 16] main <<< findGCD: 2 main <<< iterativeGCD: 2 main <<< subtractingGCD: 2
This test has five integers. They all are even so it is also easy to determine the answer.
10 112 160 180 240 28 32 480 96 60 72 main <<< n: 10 main <<< arr: [112, 160, 180, 240, 28, 32, 480, 96, 60, 72] main <<< findGCD: 4 main <<< iterativeGCD: 4 main <<< subtractingGCD: 4
In this test case we have ten numbers. They all seem even. We determine that the GCD is 4. You can check that by dividing all numbers by 4 and then determining that the remaining numbers do not have a common divisor.
8 1 2 3 5 7 11 13 17 main <<< n: 8 main <<< arr: [1, 2, 3, 5, 7, 11, 13, 17] main <<< findGCD: 1 main <<< iterativeGCD: 1 main <<< subtractingGCD: 1
I believe I went overboard with the examples. All the numbers are prime. The obvious answer is 1.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read n ****
int n = sc.nextInt();
// ???? ????
System.out.println("main <<< n: " + n);
// **** array of integers ****
int[] arr = new int[n];
// **** loop reading values ****
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// **** close scanner ****
sc.close();
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** find and display the GCD for the specified array ****
System.out.println("main <<< findGCD: " + findGCD(arr));
// **** find and display the GCD for the specified array ****
System.out.println("main <<< iterativeGCD: " + iterativeGCD(arr));
// **** find and display the GCD for the specified array ****
System.out.println("main <<< subtractingGCD: " + subtractingGCD(arr));
}
The test scaffolding is quite simple and matches what we expected to find. We read the number of integers, create an array and populate it. We then call three different functions which seem to display the same answer.
The approach in all cases is to use the Euclidean algorithm. There is a version that uses subtraction and other the modulo (%) operator. One approach is recursive while the other is iterative.
gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b)
After we figure out how to generate the GCD of two numbers we have to extend it to as many as we have in the array. That is the key observation to use in our functions.
/**
* Find the GCD of the integers in the specified array.
*/
static int findGCD(int[] arr) {
// **** ****
int result = 0;
// **** loop through the elements in the array O(n) ****
for (int e : arr) {
// **** compute the GDC between the current value and the next value in the array ****
result = gcd(result, e);
// **** ****
if (result == 1) {
return 1;
}
}
// **** ****
return result;
}
The findGCD() function gets an array of integers. It then loops through all elements by computing the GCD from the previous pair and uses for the next array element. Note that on the first pass it will use the pair a = 0 and b = arr[0]. Will see how this is used in the gcd() function shortly.
Note that if the result of the gcd() function returns a 1, we exit the loop. The reason is that the pair is only divisible by itself or 1. We should no longer proceed. You can comment out this test and the results will not vary. The algorithm will just take more time to traverse the entire array.
/**
* Find the GCD of the specified integers.
* Recursive function.
*/
static int gcd(int a, int b) {
// **** end condition ****
if (a == 0)
return b;
// **** recursive call ****
return gcd(b % a, a);
}
The gcd() function is a recursive method. It ends when the value for a == 0. That is the end condition. If that is not the care it calls itself with updated arguments.
/**
* Iterative GCD approach.
*/
static int iterativeGCD(int[] arr) {
// **** ****
int b;
int r;
// **** first value to use ****
int a = arr[0];
// **** loop once per pair of values ****
for (int i = 1; (i < arr.length) && (a > 1); i++) {
// **** current value to use ****
b = arr[i];
// **** gcd for these two values ****
while (b != 0) {
r = a % b;
a = b;
b = r;
}
}
// **** return the gcd ****
return a;
}
This code does not use recursion. After initialization it loops through the array elements computing the GCD between the running value and the current from the array. The time complexity is equal to the recursive method, but it does not make use of the memory in the stack.
/**
* Finding the GCD by subtraction.
*/
static int subtractingGCD(int[] arr) {
// **** ****
int b;
// **** first value to use ****
int a = arr[0];
// **** loop once per pair of values ****
for (int i = 1; (i < arr.length) && (a > 1); i++) {
// **** current value to use ****
b = arr[i];
// **** gcd for these two values ****
while (a != b) {
if (a > b) {
a -= b;
} else {
b -= a;
}
}
}
// **** return the gcd ****
return a;
}
If you read the Wikipedia article, you know that the original Euclidean algorithm subtracted values instead of using the modulus (%) operand. The structure of the code is quite similar with the difference in the inner loop.
In general I always like to know and experiment with algorithms instead of 
memorizing them. There is an appropriate quote attributed to Albert Einstein “Never memorize something that you can look up.” Chances are that you will forget details. I prefer to look up knowing that I am familiar with the algorithm so I will be able to implement and or ply it properly to the problem at hand. Google and Stack Overflow are your friends.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 1,602 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa