2
\$\begingroup\$

Just had this as a practice test problem and I'm curious how to optimize for performance. Thanks!

The greatest common divisor (GCD), also called the highest common factor (HCF) of N numbers is the largest positive integer that divides all numbers without giving a remainder.

Write an algorithm to determin the GCD of N positive integers.

function generalizedGCD(num, arr)
{
    // find the factors of lowest member of arr and then check if every other number is divisible
    arr.sort( function( a, b ) { return a-b; });
    const lowest = arr[0];
    const factors = [];

    for ( let i = 1; i <= lowest; i++) {
        if ( lowest % i === 0 ) {
            factors.push(i);
        }
    }

    // now check to see if each member of the factors array divides into each member of the original numbers array. If not, remove it from the array.
    for ( let j = 1; j < num; j++) {
        for ( let k = 0;  k < factors.length; k++) {
            if ( arr[j]  % factors[k] != 0 ) {
                factors.splice( k, 1);
            }
        }
    }

    return factors[factors.length-1];
}
\$\endgroup\$
1
\$\begingroup\$

I'll stick with your brute-force approach. Your code is doing more work than necessary:

  • You sort the input array. This has multiple issues.

    1. Performance-wise, you seem to sort only to get the minimum element. Just use Math.min.
    2. From an API perspective, the user of your function may be surprised to find that their input array gets sorted. Thus if you wanted to sort the array internally, you should either do a .slice() to copy the array, or at least document the mutation very explicity.
    3. The combination of num and .sort() is buggy (I presume). The num parameter seems to be there so that the user can get GCD of only a portion of the array. However, you sort the entire array, so your code is taking GCD of only the least num elements. (If this is the intended behaviour, document it.)
  • You collect an array of all the common factors, only to get the greatest. You may dispense of the factors array altogether by looping over the possible factors reversely, and immediately returning as soon as you find a suitable one. (That also avoids the potentially not-so-fast splice operation.)

Here is an updated code:

function generalizedGCD(num, arr) {
    // Use spread syntax to get minimum of array
    const lowest = Math.min(...arr);

    for (let factor = lowest; factor > 1; factor--) {
        let isCommonDivisor = true;

        for (let j = 0; j < num; j++) {
            if (arr[j] % factor !== 0) {
                isCommonDivisor = false;
                break;
            }
        }

        if (isCommonDivisor) {
            return factor;
        }
    }

    return 1;
}
\$\endgroup\$
3
\$\begingroup\$

As I am not a native in Javascript, I'll try to review your algorithm:

  • start from the lowest value and its factor is a good idea to improve speed
  • for your second loop I suggest you to start not from the lowest factor but start from the biggest factor. GCD is trying to find the biggest factor, So if you start from the biggest number, after you find a number that can divide all number in arr you can break your loop, it's more efficient.
  • I've tested it with generalizedGCD(2,[27,8]) and it returns 4 instead of 1, why? the problem is in your second loop, the size of factors changed after you delete its element and you accidentally "skip" some elements. If we try to simulate this with the example above:
    generalizedGCD(2,[8,27])
    ...
    k=0 factors=[1,2,4,8]  arr[j]=27 {27 is divisible with factors[k]=1}
    k=1 factors=[1,2,4,8]  arr[1]=27 {27 is not divisible with factors[k]=2}
    k=2 factors=[1,4,8]    arr[1]=27 {27 is not divisible with factors[k]=8} // you skipped 4
    ...
    factors=[1,4]
  • The solution that I can think is subtract k by 1 so it doesn't "move" when you are deleting an element in factors:
    if ( arr[j]  % factors[k] != 0 ) {
        factors.splice( k, 1);
        k--;
    }

Suggestion for another algorithm

I think it'll be better if you use faster algorithm: Euclid Algorithm. You can find GCD of every number in array by find GCD each two of them.

GCD( GCD( GCD(a[0], a[1]), a[2]), ...)

It's simple recursion:

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

    return gcd(b, a%b);
}

function generalizedGCD(num, arr)
{
    factors = arr[0];

    for ( let i = 1; i < num; i++) {
        factors = gcd(factors, arr[i])
    }

    return factors;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Yes always pays to test run first. Your code looks like you're a C or C++ coder. In JavaScript is very bad to not declare variables. factors is undeclared and thus becomes a global (or would throw in some contexts). Besides the point, code review is not about providing different solutions, you need to review the op's code, (it has a lot of problems you did not address) Pointing the OP to a alternative solution does not help them improve "their" code and coding skills. \$\endgroup\$ – Blindman67 Jan 31 at 1:15
  • 1
    \$\begingroup\$ @Blindman67 that's true, I'm used to code in C/C++, I only used Javascript once in a web project a few years ago, thank you so much for the suggestions. And I'm sorry, I'm new in this SE, actually I've felt I have given the wrong answer after I see how do people answer here. let this be a lesson for me. Thank you \$\endgroup\$ – malioboro Jan 31 at 1:32
  • 1
    \$\begingroup\$ Hi all, thanks for the feedback. @Malioboro, thanks for the solution -- it is in fact much more elegant than mine and I'm sure much faster. but like blindman67 said, it would in fact be much more helpful to get feedback on my code -- I'm a self-taught programmer and I have never done a formal code review at my job, ever. I'm simply trying to improve my fundamentals. :) \$\endgroup\$ – qotsa42 Jan 31 at 2:05
  • 1
    \$\begingroup\$ Another question: if the largest common divisor is 1 between the two numbers, it returns a instead of 1. How would you code that into the function? \$\endgroup\$ – qotsa42 Jan 31 at 2:59
  • 1
    \$\begingroup\$ @qotsa42 I've updated my answer \$\endgroup\$ – malioboro Jan 31 at 6:55

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.