In this article, we are given two or more numbers/array of numbers and the task is to find the GCD of the given numbers/array elements in JavaScript.
Examples:
Input : arr[] = {1, 2, 3}
Output : 1
Input : arr[] = {2, 4, 6, 8}
Output : 2
The GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCD of pairs of numbers.
gcd(a, b, c) = gcd(a, gcd(b, c))
= gcd(gcd(a, b), c)
= gcd(gcd(a, c), b)
For an array of elements, we do the following. We will also check for the result if the result at any step becomes 1 we will just return 1 as gcd(1, x) = 1.
result = arr[0] For i = 1 to n-1 result = GCD(result, arr[i])
Below is the implementation of the above approach.
Example: In this example, we will find the GCD of the elements of an array using Javascript.
Javascript
<script> // Function to return gcd of a and b function gcd(a, b) { if (a == 0) return b; return gcd(b % a, a); } // Function to find gcd of array // of numbers function findGCD(arr, n) { let result = arr[0]; for (let i = 1; i < n; i++) { result = gcd(arr[i], result); if (result == 1) { return 1; } } return result; } // Driver code let arr = [2, 4, 6, 8, 16]; let n = arr.length; console.log(findGCD(arr, n)); </script> |
Output:
2