Number of Common Factors
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through all possible candidates for a common factor and checking if they divide both a and b.
Algorithm
- Initialize a counter
countto 0. - Determine the smaller of the two numbers,
limit = min(a, b). - Loop through each integer
ifrom 1 tolimit. - Inside the loop, check if
idivides bothaandbwithout a remainder (a % i == 0 && b % i == 0). - If it does, increment the
count. - After the loop finishes, return
count.
Walkthrough
The simplest way to find common factors is to test every possible candidate. A number x can only be a common factor of a and b if it divides both. This implies that x cannot be larger than a and x cannot be larger than b. Therefore, any common factor must be less than or equal to min(a, b). We can iterate through all integers i from 1 up to min(a, b). For each i, we perform a check: if (a % i == 0 && b % i == 0). If the condition is true, we've found a common factor and we increment a counter. After checking all numbers up to min(a, b), the counter will hold the total number of common factors.
class Solution { public int commonFactors(int a, int b) { int count = 0; int limit = Math.min(a, b); for (int i = 1; i <= limit; i++) { if (a % i == 0 && b % i == 0) { count++; } } return count; }}Complexity
Time
O(min(a, b)) - The loop runs `min(a, b)` times, and each iteration involves constant time operations (modulo and comparison).
Space
O(1) - We only use a constant amount of extra space for variables like `count`, `limit`, and the loop counter `i`.
Trade-offs
Pros
Very simple to understand and implement.
Requires no advanced mathematical knowledge.
Cons
Inefficient for large values of
aandb, as the number of iterations is directly proportional to the smaller input number.
This method leverages a key mathematical property: the set of common factors of two numbers, a and b, is identical to the set of factors of their Greatest Common Divisor (GCD). This reduces the problem to finding the number of factors of a single, smaller number, which can be done efficiently.
Algorithm
- Calculate the Greatest Common Divisor (GCD) of
aandb. Let this beg. An efficient way is using the Euclidean algorithm. - Initialize a factor counter
countto 0. - Iterate with a loop variable
ifrom 1 up to the integer part of the square root ofg. - For each
i, check ifg % i == 0. - If it is, we have found factors:
- If
i * i == g, theniis the square root, and we have found one unique factor. Incrementcountby 1. - Otherwise,
iandg/iare a pair of distinct factors. Incrementcountby 2.
- If
- After the loop, return
count.
Walkthrough
A more efficient method is based on the mathematical insight that any common divisor of a and b must also be a divisor of their Greatest Common Divisor (GCD). Conversely, any divisor of gcd(a, b) is a common divisor of a and b. Therefore, the problem is equivalent to finding the number of divisors of gcd(a, b).
The algorithm proceeds in two steps:
- Calculate GCD: First, we find the GCD of
aandb, let's call itg. The Euclidean algorithm is a highly efficient method for this. - Count Factors of GCD: Next, we count the number of factors of
g. A standard optimization for counting factors is to iterate only up to the square root ofg. For each numberithat dividesg, we know thatg/iis also a factor. Ifiis the square root ofg,iandg/iare the same, so we count it once. Otherwise, we have found a pair of distinct factors (iandg/i), so we add two to our count.
class Solution { // Helper function to compute GCD using Euclidean algorithm private int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } public int commonFactors(int a, int b) { int g = gcd(a, b); int count = 0; for (int i = 1; i * i <= g; i++) { if (g % i == 0) { // i is a factor, so g/i is also a factor. if (i * i == g) { // If i is the square root, we count it once. count++; } else { // Otherwise, we count both i and g/i. count += 2; } } } return count; }}Complexity
Time
O(sqrt(min(a, b))) - The Euclidean algorithm for GCD takes `O(log(min(a, b)))` time. The main work is counting factors of the GCD, `g`, which takes `O(sqrt(g))` time. Since `g <= min(a, b)`, the overall complexity is dominated by `O(sqrt(g))`, which is bounded by `O(sqrt(min(a, b)))`.
Space
O(1) - The iterative Euclidean algorithm uses constant space. The factor counting loop also uses constant extra space.
Trade-offs
Pros
Significantly more efficient, with a time complexity related to the square root of the input values.
Scales well for larger numbers beyond the given constraints.
Cons
Slightly more complex due to the need to implement or use a GCD function.
Requires understanding of number theory concepts (GCD and its properties).
Solutions
Solution
class Solution {public int commonFactors(int a, int b) { int g = gcd(a, b); int ans = 0; for (int x = 1; x <= g; ++x) { if (g % x == 0) { ++ans; } } return ans; }private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }}class Solution {public: int commonFactors(int a, int b) { int g = gcd(a, b); int ans = 0; for (int x = 1; x <= g; ++x) { ans += g % x == 0; } return ans; }};class Solution: def commonFactors(self, a: int, b: int) -> int: g = gcd(a, b) return sum(g % x == 0 for x in range(1, g + 1))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.