Data Structures & Algorithms Multiple Choice Questions on “GCD and LCM using Recursion – 1”.
1. Which of the following is not another name for GCD(Greatest Common Divisor)? Answer: a 2. What is the GCD of 8 and 12? Answer: d 3. If GCD of two number is 8 and LCM is 144, then what is the second number if first number is 72? Answer: d 4. Which of the following is also known as GCD? 5. Which of the following is coprime number? 6. In terms of Venn Diagram, which of the following expression gives GCD (Given A ꓵ B ≠ Ø)? Answer: b 7. What is the GCD according to the given Venn Diagram? Answer: c 8. What is the GCD of a and b? Answer: b 9. What is the GCD of 48, 18, 0? Answer: d 10. Is 9 and 28 coprime number? Answer: a 11. If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then what is the expression called? Answer: a 12. Is gcd an associative function. Answer: a 13. Which is the correct term of the given relation, gcd (a, b) * lcm (a, b) =? Answer: a 14. Who gave the expression for the probability and expected value of gcd? Answer: a 15. What is the computational complexity of Binary GCD algorithm where a and b are integers? Answer: a
a) LCM
b) GCM
c) GCF
d) HCF
Clarification: : LCM (Least Common Multiple) and GCD are not same. GCM (Greatest Common Measure), GCF (Greatest Common Factor), HCF (Highest Common Factor) are other names for GCD.
a) 8
b) 12
c) 2
d) 4
Clarification: GCD is largest positive integer that divides each of the integer. So the GCD of 8 and 12 is 4.
a) 24
b) 2
c) 3
d) 16
Clarification: As A * B = GCD (A, B) * LCM (A, B). So B = (144 * 8)/72 = 16.
a) Highest Common Divisor
b) Highest Common Multiple
c) Highest Common Measure
d) Lowest Common Multiple
Answer: a
Clarification: GCM (Greatest Common Measure), GCF (Greatest Common Factor), HCF (Highest Common Factor) and HCF (Highest Common Divisor) are also known as GCD.
a) 54 and 24
b) 4 and 8
c) 6 and 12
d) 9 and 28
Answer: d
Clarification: Coprime numbers have GCD 1. So 9 and 28 are coprime numbers. While 54 and 24 have GCD 6, 4 and 8 have GCD 4, 6 and 12 have GCD 6.
a) Multiplication of A U B terms
b) Multiplication of A ꓵ B terms
c) Multiplication of A*B terms
d) Multiplication of A-B terms
Clarification: In terms of Venn Diagram, the GCD is given by the intersection of two sets. So A ꓵ B gives the GCD. While A U B gives the LCM.
a) 2
b) 3
c) 5
d) 6
Clarification: In terms of Venn Diagram, the GCD is given by the intersection of two sets. So A ꓵ B gives the GCD. While A U B gives the LCM. So here A ꓵ B is 5.
a) a + b
b) gcd (a-b, b) if a>b
c) gcd (a+b, a-b)
d) a – b
Clarification: As per Euclid’s Algorithm, gcd (a, b) = gcd (a-b, b) if a > b or gcd (a, b) = gcd (a, b-a) if b > a.
a) 24
b) 2
c) 3
d) 6
Clarification: GCD is largest positive integer that divides each of the integer. So the GCD of 48, 18, 0 is 6.
a) True
b) False
Clarification: Coprime numbers have GCD 1. So 9 and 28 are coprime numbers.
a) Bezout’s Identity
b) Multiplicative Identity
c) Sum of Product
d) Product of Sum
Clarification: If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then the expression is called Bezout’s Identity and p, q can be calculated by extended form of Euclidean algorithm.
a) True
b) False
Clarification: The gcd function is an associative function as gcd (a, gcd (b, c)) = gcd (gcd (a, b), c).
a) |a*b|
b) a + b
c) a – b
d) a / b
Clarification: The gcd is closely related to lcm as gcd (a, b) * lcm (a, b) = |a*b|.
a) James E. Nymann
b) Riemann
c) Thomae
d) Euler
Clarification: In the year 1972, James E. Nymann showed some result to show the probability and expected value of gcd.
a) O (log a + log b)2)
b) O (log (a + b))
c) O (log ab)
d) O (log a-b)
Clarification: From the Binary GCD algorithm, it is found that the computational complexity is O (log a + log b)2) as the total number of steps in the execution is at most the total sum of number of bits of a and b.