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 papers with video solutions PDF
5000+ Topic-wise Previous year CAT Solved Questions for Free

CAT Quant Questions | CAT Quantitative Ability

CAT Venn Diagrams Questions CAT Simple Interest Compound Interest Questions CAT Remainders Questions CAT Linear Equations Questions CAT Coordinate Geometry Questions

CAT DILR Questions | LRDI Questions For CAT

CAT Truth Lie Concept Questions CAT Quant Based LR Questions CAT Quant Based DI Questions CAT Charts Questions CAT Scheduling Questions

CAT Verbal Ability Questions | VARC Questions For CAT

CAT Para Jumbles Questions CAT Reading Comprehension Questions CAT Verbal Ability Questions CAT Odd One Out Questions CAT Critical Reasoning Questions

CAT 1999 QA Question

CAT Quant Questions | CAT Quantitative Ability

CAT DILR Questions | LRDI Questions For CAT

CAT Verbal Ability Questions | VARC Questions For CAT

Free Quant Questions

Login to your Cracku account

Hello! 👋

Ready to Unlock Your Success?

Please Enter Your OTP

Please enter the following details

Create a free Cracku account