CAT Quantitative Ability Questions | CAT Functions questions
CAT/1999
Question . 63
There is a set of 'n' natural numbers. The function 'H' is such that it finds the highest common factor between any two numbers. What is the minimum number of times that the function has to be invoked to find the H.C.F. of the given set of numbers?
View Answer
Explanatory Answer
Method of solving this CAT Quantitative Ability Question from Functions question
(b) Out of n numbers, HCF of 1st and 2nd numbers can be calculated by invoking the function once.
Then HCF of this HCF and 3rd number can be calculated by invoking the function 2nd time and so on.
Each time the function is invoked, instead of two numbers we are left with one, i.e., one number is eliminated.
Getting the final HCF means eliminating (n – 1) numbers and thus function has to be invoked (n – 1) times.