Number of Common Factors — Solution in Python, Java & C++
Number of Common Factors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Number of Common Factors is an easy coding problem on math, enumeration and number theory, asked in Amazon and Infosys interviews.
- Difficulty: Easy
- Topics: Math, Enumeration, Number Theory
- Asked at: Amazon, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two positive integers a and b, return the number of common factors they share.
An integer x is a common factor if it divides both a and b exactly.
Example 1
Input: a = 12, b = 6
Output: 4
Explanation: The common factors are 1, 2, 3 and 6.
Example 2
Input: a = 25, b = 30
Output: 2
Explanation: The common factors are 1 and 5.
Example 3
Input: a = 7, b = 13
Output: 1
Constraints
1 <= a, b <= 1000
Hints for Number of Common Factors
Hint 1
A common factor cannot exceed the smaller of the two numbers.
Hint 2
Test every candidate from 1 up to
min(a, b).Hint 3
Equivalently, the answer is the number of divisors of
gcd(a, b).
How to solve Number of Common Factors
The common factors of a and b are exactly the divisors of gcd(a, b), but with both values bounded by 1000 a direct scan is simplest.
Approach
- Loop
dfrom 1 tomin(a, b). - Count
dwhen it divides bothaandb.
Why it works
d | a and d | b together are equivalent to d | gcd(a, b), so the scan counts precisely the divisors of the gcd — the same answer either way.
Complexity
- Time —
O(min(a, b)) - Space —
O(1)
Pitfalls
- Looping to
max(a, b)wastes work and can never find an extra factor. - 1 is always a common factor, so the answer is never 0.
Reference solution
Python
def commonFactors(a: int, b: int) -> int:
return sum(1 for d in range(1, min(a, b) + 1) if a % d == 0 and b % d == 0)Java
public static int commonFactors(int a, int b) {
int m = Math.min(a, b);
int count = 0;
for (int d = 1; d <= m; d++) {
if (a % d == 0 && b % d == 0) count++;
}
return count;
}C++
int commonFactors(int a, int b) {
int m = min(a, b);
int count = 0;
for (int d = 1; d <= m; d++) {
if (a % d == 0 && b % d == 0) count++;
}
return count;
}JavaScript
var commonFactors = function(a, b) {
const m = Math.min(a, b);
let count = 0;
for (let d = 1; d <= m; d++) {
if (a % d === 0 && b % d === 0) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.