In this guide, you will get 2427. Number of Common Factors LeetCode Solution with the best time and space complexity. The solution to Number of Common Factors problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given two positive integers a and b, return the number of common factors of a and b.
An integer x is a common factor of a and b if x divides both a and b.
Example 1:
Input: a = 12, b = 6
Output: 4
Explanation: The common factors of 12 and 6 are 1, 2, 3, 6.
Example 2:
Input: a = 25, b = 30
Output: 2
Explanation: The common factors of 25 and 30 are 1, 5.
Constraints:
1 <= a, b <= 1000
Complexity Analysis
Time Complexity: O(\texttt{gcd(a, b)})
Space Complexity: O(1)
2427. Number of Common Factors LeetCode Solution in C++
class Solution {
public:
int commonFactors(int a, int b) {
int ans = 1;
const int gcd = __gcd(a, b);
for (int i = 2; i <= gcd; ++i)
if (a % i == 0 && b % i == 0)
++ans;
return ans;
}
}; /* code provided by PROGIEZ */
2427. Number of Common Factors LeetCode Solution in Java
class Solution {
public int commonFactors(int a, int b) {
int ans = 1;
final int gcd = gcd(a, b);
for (int i = 2; i <= gcd; ++i)
if (a % i == 0 && b % i == 0)
++ans;
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
} // code provided by PROGIEZ
2427. Number of Common Factors LeetCode Solution in Python
class Solution:
def commonFactors(self, a: int, b: int) -> int:
gcd = math.gcd(a, b)
return sum(a % i == 0 and b % i == 0
for i in range(1, gcd + 1)) # code by PROGIEZ
