Number of Common Factors - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: Given two integers a and b, return how many integers divide both numbers without leaving a remainder. A number is a common factor if a % x == 0 and b % x == 0.
Approach 1: Direct Iteration (Time: O(min(a,b)), Space: O(1))
The straightforward solution checks every possible factor from 1 to min(a, b). For each integer i, verify whether it divides both numbers using the modulo operation. If a % i == 0 and b % i == 0, increment the count. This brute-force enumeration works because any common factor cannot exceed the smaller number. The method relies purely on enumeration and basic math operations.
This approach is easy to implement and perfectly fine for small constraints. It demonstrates clear understanding of factor checking, which interviewers often expect before discussing optimizations.
Approach 2: Using GCD (Time: O(sqrt(g)), Space: O(1))
A key observation: any number that divides both a and b must also divide g = gcd(a, b). Instead of checking all numbers up to min(a,b), compute the greatest common divisor using the Euclidean algorithm from number theory. The problem then reduces to counting how many divisors g has.
To count divisors efficiently, iterate from 1 to sqrt(g). If i divides g, then both i and g / i are valid divisors (unless they are equal). Each divisor corresponds to a number that divides both a and b. This reduces the search space significantly compared to scanning all numbers up to min(a,b).
Recommended for interviews: Start with direct iteration to show you understand what a common factor means. Then move to the GCD-based solution. Using gcd(a,b) and enumerating its divisors cuts the complexity to O(sqrt(g)), which demonstrates stronger algorithmic thinking and familiarity with number theory optimizations.
Approach 1: Approach 1: Direct Iteration
In this approach, we iterate over the numbers from 1 to the minimum of the two numbers. For each number, we check if it divides both a and b. If it does, we increment the count of common factors.
This approach leverages the fact that no number larger than the smaller of a and b can be a common factor.
This C code defines a function commonFactors that calculates the number of common factors by iterating from 1 to the minimum of a and b. For each integer i, it checks if both a and b are divisible by i and counts such numbers.
Complexity
Time Complexity: O(min(a, b))
Space Complexity: O(1)
Approach 2: Approach 2: Using GCD
This approach leverages the greatest common divisor (GCD) of a and b. The common factors of two numbers cannot exceed their GCD. Thus, by finding the GCD, we only need to consider the factors of the GCD as potential common factors.
Once we determine the GCD, we iterate through numbers from 1 up to this GCD to count its divisors.
This C implementation first computes the GCD of a and b using the Euclidean algorithm. Then it finds the divisors of this GCD, which are also the common factors of a and b.
Complexity
Time Complexity: O(log(min(a, b)) + G)
Space Complexity: O(1)
Where G is the number of divisors of the GCD.
Approach 3: Enumeration
We can first calculate the greatest common divisor g of a and b, then enumerate each number in [1,..g], check whether it is a factor of g, if it is, then increment the answer by one.
The time complexity is O(min(a, b)), and the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Approach 4: Optimized Enumeration
Similar to Solution 1, we can first calculate the greatest common divisor g of a and b, then enumerate all factors of the greatest common divisor g, and accumulate the answer.
The time complexity is O(\sqrt{min(a, b)}), and the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Direct Iteration | Time Complexity: O(min(a, b)) |
| Approach 2: Using GCD | Time Complexity: O(log(min(a, b)) + G) Where G is the number of divisors of the GCD. |
| Enumeration | — |
| Optimized Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Iteration | O(min(a,b)) | O(1) | Simple implementation when numbers are small or constraints are low |
| Using GCD + Divisor Enumeration | O(sqrt(g)) | O(1) | Preferred optimized approach when numbers are larger and divisor counting is faster |
Video Solution
2427. Number of Common Factors | LEETCODE EASY • code Explainer • 919 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Common Factors easy or hard?
Number of Common Factors Python/Java solution
How to solve Number of Common Factors in O(sqrt(n))?
What is the best approach for Number of Common Factors?
Is Number of Common Factors asked at Google/Amazon/Meta?
What data structure is used in Number of Common Factors?
What is the time complexity of Number of Common Factors?
Ready to solve this problem?
Practice Number of Common Factors with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor