Question 12

For two positive integers a and b define the function h(a,b):as the greatest common factor (G.C.F) 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:

Solution

Let p and q be any two elements of the set A.
For the computation of the GCF of elements of the set A, we can replace both p and q by just the GCF(p,q) and the result is unchanged.

So, for every application of the function h, we are reducing the number of elements of the set A by 1. (In this case two numbers p and q are replaced by one number GCF(p,q)).
Expanding this concept further, the minimum number of times the function h should be called is n-1


Create a FREE account and get:

  • All Quant CAT complete Formulas and shortcuts PDF
  • 35+ CAT previous year papers with video solutions PDF
  • 5000+ Topic-wise Previous year CAT Solved Questions for Free

cracku

Boost your Prep!

Download App