GCD (Greatest Common Divisor) – Practice Problems
1. Find the GCD of two given positive integers.
Example:
Input:
48 18
Output:
6
2. Find the GCD of three numbers.
Example:
Input:
24 36 60
Output:
12
3. Find the GCD of N numbers.
Example:
Input:
5
12 18 24 30 42
Output:
6
4. Check whether two numbers are Coprime.
Example:
Input:
14 25
Output:
Coprime
Input:
12 18
Output:
Not Coprime
5. Simplify a Fraction using GCD.
Example:
Input:
24 36
Output:
2/3
6. Find the Least Common Multiple (LCM) using GCD.
Example:
Input:
12 18
Output:
36
7. Find the largest number that divides both numbers exactly.
Example:
Input:
56 98
Output:
14
8. Find the GCD of an array.
Example:
Input:
4
8 12 20 28
Output:
4
9. Find the GCD of factorials.
Example:
Input:
57
Output:
120
Explanation:
GCD(5!, 7!) = 5!
10. Find the GCD of all even numbers in an array.
Example:
Input:
6
4 8 9 12 16 25
Output:
4
11. Find the GCD of all odd numbers in an array.
Example:
Input:
5
15 21 35 49 63
Output:
7
12. Count pairs having GCD equal to 1.
Example:
Input:
4
2345
Output:
5
13. Find the maximum GCD among all pairs in an array.
Example:
Input:
5
2 4 6 8 10
Output:
4
14. Replace every pair with its GCD until one number remains.
Example:
Input:
12 18 24
Output:
6
15. Find the GCD of two very large numbers given as strings.
Example:
Input:
"123456789123456789"
"987654321987654321"
Output:
9
16. Find the minimum operations to make two numbers equal using GCD.
17. Find all common divisors of two numbers.
Example:
Input:
24 36
Output:
1 2 3 4 6 12
18. Print the GCD after every query.
Example:
Array:
12 18 24
Queries:
GCD(12,18)
GCD(18,24)
19. Find the GCD of numbers from L to R in an array.
20. Given two numbers A and B, find whether their GCD is a prime number.
21. Find the largest subset whose GCD is greater than 1.
22. Find the smallest positive number that should be added to make the GCD greater than 1.
23. Find the GCD of adjacent elements in an array.
24. Find the longest subarray having GCD greater than 1.
25. Find the number of divisors of the GCD of two numbers.
26. Find the sum of all common divisors of two numbers.
27. Find the GCD of two binary numbers.
28. Given N numbers, remove one element so that the GCD of the remaining elements is
maximum.
29. Find the maximum possible GCD after changing one array element.
30. Given two numbers A and B, repeatedly subtract the smaller from the larger until both
become equal. Print the final number (Hint: GCD).
FAST EXPONENTIATION (BINARY EXPONENTIATION) - PRACTICE PROBLEMS
1. Calculate A^B using Fast Exponentiation.
2. Calculate (A^B) % M using Binary Exponentiation.
3. Find the last digit of A^B.
4. Find the last two digits of A^B.
5. Check whether A^B is even or odd.
6. Compute A^B where B can be as large as 10^18.
7. Compute A^B where A and B are given as user input.
8. Calculate X^N recursively using Fast Exponentiation.
9. Calculate X^N iteratively using Fast Exponentiation.
10. Find the number of multiplications required to compute A^B using Binary Exponentiation.
11. Compare Normal Exponentiation and Fast Exponentiation by counting the number of
operations.
12. Compute (A^B) % 1000000007.
13. Calculate the modular inverse of A using Fast Exponentiation.
14. Find (A^B + C^D) % M.
15. Find (A^B × C^D) % M.
16. Find (A^B - C^D) % M.
17. Compute the power of every element in an array.
18. Given N queries, each containing A and B, print A^B efficiently.
19. Find the smallest exponent B such that A^B is greater than or equal to X.
20. Calculate powers of a matrix using Fast Exponentiation.
21. Compute Fibonacci(N) using Matrix Fast Exponentiation.
22. Calculate Decimal to Binary using repeated powers of 2.
23. Find whether A^B is divisible by K.
24. Compute (2^N - 1) using Fast Exponentiation.
25. Find the sum of powers:
A^1 + A^2 + A^3 + ... + A^N.
26. Find the product of powers:
A^1 × A^2 × ... × A^N.
27. Calculate X^(2^N).
28. Find the maximum value among A^B for N pairs.
29. Sort pairs based on the value of A^B.
30. Given A, B, and C, determine whether A^B > C.
31. Find the first exponent B such that A^B ends with digit 6.
32. Find the first exponent B such that A^B becomes greater than 10^9.
33. Find A^(B!) using Modular Exponentiation.
34. Compute (A^B) modulo a prime number.
35. Calculate the power of complex numbers using Binary Exponentiation.
36. Find the largest power of 2 less than or equal to N.
37. Check whether a number is a perfect power.
38. Find the nearest power of 2 greater than or equal to N.
39. Count how many powers of 2 lie between L and R.
40. Given N numbers, compute the square of each number using Fast Exponentiation.