Question

For two positive integers a and b define the function h(a, b) as the greatest common factor (gcf) of a, b. Let A be a set of n positive integers, G(A), the gcf of the elements of set A is computed by repeatedly using the function h. The minimum number of times h is required to be used to compute G is:

• A. n/2
• B. n - 1
• C. n
• D. None of these

Hint:

For GCF calculations, the minimum number of operations is achieved by reducing the problem pair by pair.

Answer 1

The Correct Option is B

The minimum number of operations required to compute the GCF of n numbers is n-1, as we need to repeatedly find the GCF of pairs of numbers.