Course: JavaScript

Progress (0%)

  1. Foundation

  2. Numbers

  3. Strings

  4. Conditions

  5. Loops

  6. Arrays

  7. Functions

  8. Objects

  9. Exceptions

  10. HTML DOM

  11. CSSOM

  12. Events

  13. Drag and Drop

  14. opt Touch Events

  15. Misc

  16. Project: Analog Clock

Exercise: Greatest Common Divisor

Exercise 25 Easy

Prerequisites for the exercise

  1. JavaScript for Loop
  2. All previous chapters

Objective

Create a function to find the greatest common divisor of two integers.

Description

The greatest common divisor, or simply the gcd, of two non-negative integers ::a:: and ::b:: is the largest integer that divides both ::a:: and ::b::.

For instance, the greatest common divisor of ::10:: and ::20:: is ::10::. This is often written as ::\text{gcd}(10, 20) = 10::. All common divisors of ::10:: and ::20:: are ::1, 2, 5, 10::, where the largest value is ::10::. Hence, ::\text{gcd}(10, 20) = 10::.

Similarly, ::\text{gcd}(10, 3) = 1::. There is no common divisor of ::10:: and ::3:: except for ::1::, hence, it's the greatest common divisor. Such a pair of integers whose gcd is ::1:: are said to be relatively prime to each other.

As another example, ::\text{gcd}(10, 0) = 10::. On the same lines, ::\text{gcd}(0, 10) = 10:: as well. However, ::\text{gcd}(0, 0):: is undefined. Every integer can divide ::0::, and so likewise there is no limit to this expression.

In this exercise, you have to create a function gcd() that takes in two integers as arguments and returns back their gcd. If both the numbers are 0, the function should return Infinity.

You MUST implement a brute force algorithm using for that goes over every integer to see if it's a common divisor or not.

Here's an example of the usage of the function:

gcd(10, 20)
10
gcd(20, 20)
20
gcd(10, 0)
10
gcd(0, 10)
10
gcd(0, 0)
Infinity
View Solution

New file

Inside the directory you created for this course on JavaScript, create a new folder called Exercise-25-Greatest-Common-Divisor and put the .html solution files for this exercise within it.

Solution

First, let's deal with some simple cases as described below:

  1. If both the integers are 0, we return Infinity.
  2. If only one integer is 0, we return the other integer.

Here's the implementation of these simple cases:

function gcd(a, b) {
   if (a === 0 && b === 0) {
      return Infinity;
   }

   if (a === 0 || b === 0) {
      return a + b;
   }
}

If a === 0 && b === 0 evaluates to true, that simply means that both a and b are 0; likewise we return Infinity.

If this is not the case, then it might be that one of the integers is 0. This is checked by the expression a === 0 || b === 0. If it evaluates to true, we return a + b.

Now this is kind of a shortcut. Let's see how.

We know that one of the integers is 0 and have to return the other one. A quick way is to return the sum of both the numbers, one of which is non-zero. The sum would obviously be that non-zero value which is our gcd.

So far, so good.

Next up, if neither of the cases above is met, we move to a loop to perform the computation.

In the loop, we need to iterate upto the minimum of the given arguments a and b (including that value) in search of all common divisors of a and b. Whenever we find one, we update the previously-known common divisor with this new integer. In the end, this common divisor is returned.

Altogether, we get to the following code:

function gcd(a, b) {
   if (a === 0 && b === 0) {
      return Infinity;
   }

   if (a === 0 || b === 0) {
      return a + b;
   }

   var limit = Math.min(a, b);
   var commonDivisor = 1;

   for (var i = 2; i <= limit; i++) {
      if (a % i === 0 && b % i === 0) {
         commonDivisor = i;
      }
   }

   return commonDivisor;
}

limit holds the upper limit of the loop counter variable i, which is simply the minimum of the two values a and b. We choose the minimum because if we go higher than that, the smaller of a and b won't be divisible by that larger value.

For instance, if a = 50 and b = 1000, there is absolutely no point of searching for common divisors of a and b above 50 since all those numbers won't divide 50 (which is the minimum value in this case).

The loop goes from i = 2 to i = limit in search of common divisors of a and b. The reason why we don't start from i = 0 is quite apparent — 0 can't be a divisor! Moreover, the reason why at i = 1 is because we already know that regardless of what integers we choose, 1 would always be their common divisor.

Whenever a common divisor is noticed, the variable commonDivisor is updated to this new integer. In the end, this integer is the largest common divisor and that's exactly what's returned back by the function.