Find Greatest Common Divisor of Array

Find Greatest Common Divisor of Array

What is this problem about?

The Find Greatest Common Divisor of Array coding problem asks you to identify the Greatest Common Divisor (GCD) of the smallest and largest numbers in a given integer array. You are not required to find the GCD of all elements, just the extremes. The GCD is the largest positive integer that divides both numbers without leaving a remainder.

Why is this asked in interviews?

Companies like Google and Bloomberg use this Find Greatest Common Divisor of Array interview question to evaluate a candidate's grasp of basic Number Theory and Array interview patterns. It tests your ability to perform efficient linear scans to find extremum values and your knowledge of the Euclidean algorithm, which is a fundamental tool in algorithmic efficiency.

Algorithmic pattern used

This problem combines Linear Scan with the Euclidean Algorithm.

1. Initialize minVal and maxVal with the first element or extreme integer limits.
2. Iterate through the array once to find the actual minimum and maximum values ($O(n)$).
3. Apply the Euclidean algorithm: while(b != 0): a, b = b, a % b. The result a is the GCD.

Example explanation

Array: [2, 5, 6, 9, 10]

1. Find extremes: minVal = 2, maxVal = 10.
2. Calculate GCD(2, 10):
   • $10 \pmod 2 = 0$.
   • The divisor was 2. Result: 2.

Array: [7, 5, 6, 8]

1. Find extremes: minVal = 5, maxVal = 8.
2. Calculate GCD(5, 8):
   • $8 \pmod 5 = 3$
   • $5 \pmod 3 = 2$
   • $3 \pmod 2 = 1$
   • $2 \pmod 1 = 0$ Result: 1.

Common mistakes candidates make

• GCD of all elements: Misreading the prompt and trying to find the GCD of the entire array, which is a different (though related) problem.
• Inefficient GCD: Using a brute-force approach (looping from minVal down to 1) instead of the logarithmic Euclidean algorithm.
• Sorting: Sorting the array to find the min and max ($O(n \log n)$) when a simple $O(n)$ pass is sufficient.

Interview preparation tip

Always remember the Euclidean algorithm. It is the gold standard for GCD problems and appears in everything from fraction simplification to cryptography challenges.