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 <= 1000In #2427 Number of Common Factors, the task is to count how many integers divide both given numbers. A straightforward idea is to iterate from 1 to min(a, b) and check whether each value divides both numbers. While simple, this approach becomes inefficient when the numbers are large.
A more optimal strategy uses a key number theory observation: any common factor of two numbers must also be a factor of their greatest common divisor (GCD). First compute gcd(a, b) using the Euclidean algorithm. Then count how many divisors the GCD has. Instead of checking every number up to the GCD, iterate only up to sqrt(gcd) and count factor pairs, which significantly reduces the number of checks.
This approach leverages GCD + divisor enumeration to efficiently compute the result with minimal extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force (check up to min(a, b)) | O(min(a, b)) | O(1) |
| GCD + Divisor Enumeration | O(sqrt(gcd(a, b))) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
For each integer in range [1,1000], check if it’s divisible by both A and B.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Any number that divides both integers must also divide their greatest common divisor. By reducing the problem to counting the divisors of the GCD, we avoid checking unnecessary numbers and improve efficiency.
Yes, similar problems appear in coding interviews to test understanding of number theory concepts like GCD and divisor counting. It is especially common in entry-level or easy-level interview rounds.
The optimal approach first computes the GCD of the two numbers using the Euclidean algorithm. Then it counts the number of divisors of that GCD by iterating up to its square root and considering divisor pairs.
No special data structure is required for this problem. The solution relies mainly on mathematical operations such as computing the GCD and enumerating divisors using simple loops.