LeetCode 2427 - Number of Common Factors

The problem gives us two positive integers, a and b, and asks us to count how many integers divide both numbers evenly. A number x is considered a common factor if: - a % x == 0 - b % x == 0 This means x divides both integers without leaving a remainder.

leetcodeeasymathenumerationnumber-theory

LeetCode Problem 2427

Difficulty: 🟢 Easy
Topics: Math, Enumeration, Number Theory

Solution

Problem Understanding

The problem gives us two positive integers, a and b, and asks us to count how many integers divide both numbers evenly.

A number x is considered a common factor if:

  • a % x == 0
  • b % x == 0

This means x divides both integers without leaving a remainder.

For example, if a = 12 and b = 6, the common factors are:

  • 1, because both numbers are divisible by 1
  • 2, because both numbers are divisible by 2
  • 3, because both numbers are divisible by 3
  • 6, because both numbers are divisible by 6

So the answer is 4.

The input constraints are small:

  • 1 <= a, b <= 1000

Because the numbers are at most 1000, even relatively simple enumeration approaches are fast enough. This is important because it means we do not need advanced number theory optimizations to pass the problem efficiently.

The key observation is that any common factor of a and b must divide both numbers. Another way to think about this is that every common factor must also divide gcd(a, b).

Important edge cases include:

  • When both numbers are 1, the only common factor is 1
  • When the numbers are coprime, the answer should be 1
  • When both numbers are equal, every factor of the number is a common factor
  • When one number divides the other exactly, the common factors are simply the factors of the smaller number that also divide the larger one

Because the inputs are guaranteed to be positive integers, we do not need to handle zero or negative values.

Approaches

Brute Force Approach

The most direct solution is to check every integer from 1 up to min(a, b).

For each candidate number i:

  • Check whether a % i == 0
  • Check whether b % i == 0

If both conditions are true, then i is a common factor, so we increment the answer.

This approach is correct because no factor larger than min(a, b) can divide both numbers. By checking every possible candidate in that range, we guarantee that we count every common factor exactly once.

Although this is called a brute force approach, it is completely acceptable for the given constraints because the maximum range is only 1000.

Optimal Approach

A better mathematical observation is that all common factors of a and b are precisely the factors of gcd(a, b).

If we compute:

$g = \gcd(a,b)$

then every common factor must divide g.

So instead of checking factors against both a and b, we can:

  1. Compute the greatest common divisor
  2. Count how many divisors the GCD has

This reduces redundant divisibility checks and expresses the problem more cleanly using number theory.

Since the constraints are tiny, we can simply enumerate all integers from 1 to g and count the divisors.

Approach Time Complexity Space Complexity Notes
Brute Force O(min(a, b)) O(1) Checks every possible factor against both numbers
Optimal O(gcd(a, b)) O(1) Computes GCD first, then counts divisors of the GCD

Algorithm Walkthrough

Optimal Algorithm

  1. Compute the greatest common divisor of a and b.

The GCD represents the largest number that divides both integers. Every common factor of a and b must also divide the GCD. 2. Store the GCD in a variable called common_divisor.

This value becomes the only number we need to analyze further. 3. Initialize a counter variable count to 0.

This variable will track how many divisors the GCD has. 4. Iterate from 1 to common_divisor inclusive.

Every divisor of the GCD corresponds to a common factor of the original two numbers. 5. For each number i, check whether:

common_divisor % i == 0

If true, then i divides the GCD evenly, meaning it is a common factor of both a and b. 6. Increment count whenever a valid divisor is found. 7. Return count after the loop finishes.

Why it works

The correctness comes from a fundamental property of divisibility:

$x \mid a \text{ and } x \mid b \iff x \mid \gcd(a,b)$

This means the set of common factors of a and b is exactly the set of divisors of their GCD. By counting the divisors of the GCD, we count all common factors correctly.

Python Solution

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        def gcd(x: int, y: int) -> int:
            while y:
                x, y = y, x % y
            return x
        
        common_divisor = gcd(a, b)
        count = 0
        
        for i in range(1, common_divisor + 1):
            if common_divisor % i == 0:
                count += 1
        
        return count

The implementation begins by defining a helper function to compute the greatest common divisor using the Euclidean algorithm.

The Euclidean algorithm repeatedly replaces:

(x, y)

with:

(y, x % y)

until y becomes zero. At that point, x contains the GCD.

After computing the GCD, the code iterates through every integer from 1 to common_divisor.

Whenever a number divides the GCD evenly, it is counted as a valid common factor.

Finally, the function returns the total count.

The implementation follows the exact logic described in the algorithm walkthrough and uses only constant extra space.

Go Solution

func commonFactors(a int, b int) int {
    gcd := func(x int, y int) int {
        for y != 0 {
            x, y = y, x%y
        }
        return x
    }

    commonDivisor := gcd(a, b)
    count := 0

    for i := 1; i <= commonDivisor; i++ {
        if commonDivisor%i == 0 {
            count++
        }
    }

    return count
}

The Go implementation mirrors the Python solution closely.

Go does not support nested named functions in the same way as Python, so the GCD helper is implemented as an anonymous function assigned to a variable.

Integer overflow is not a concern because the constraints are very small. The solution uses only integer arithmetic and constant extra memory.

Worked Examples

Example 1

Input:

a = 12
b = 6

First compute the GCD:

$\gcd(12,6)=6$

Now count the divisors of 6.

i 6 % i Is Divisor? Count
1 0 Yes 1
2 0 Yes 2
3 0 Yes 3
4 2 No 3
5 1 No 3
6 0 Yes 4

Final answer:

4

Example 2

Input:

a = 25
b = 30

First compute the GCD:

$\gcd(25,30)=5$

Now count the divisors of 5.

i 5 % i Is Divisor? Count
1 0 Yes 1
2 1 No 1
3 2 No 1
4 1 No 1
5 0 Yes 2

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(gcd(a, b)) We iterate from 1 to the GCD and perform constant time checks
Space O(1) Only a few integer variables are used

The Euclidean algorithm for computing the GCD is extremely fast and runs in logarithmic time, but the divisor counting loop dominates the runtime. Since the maximum possible GCD is 1000, the algorithm is easily efficient enough for the problem constraints.

Test Cases

solution = Solution()

assert solution.commonFactors(12, 6) == 4   # basic example
assert solution.commonFactors(25, 30) == 2  # coprime except for 1 and 5

assert solution.commonFactors(1, 1) == 1    # smallest possible inputs
assert solution.commonFactors(2, 3) == 1    # coprime numbers
assert solution.commonFactors(10, 10) == 4  # equal numbers

assert solution.commonFactors(1000, 1000) == 16  # many divisors
assert solution.commonFactors(7, 14) == 2        # one number divides the other
assert solution.commonFactors(17, 19) == 1       # distinct primes

assert solution.commonFactors(36, 48) == 6       # multiple shared divisors
assert solution.commonFactors(81, 27) == 4       # powers of the same prime
Test Why
(12, 6) Verifies the provided example
(25, 30) Verifies partial overlap of factors
(1, 1) Tests smallest valid inputs
(2, 3) Tests coprime numbers
(10, 10) Tests identical inputs
(1000, 1000) Tests upper constraint boundary
(7, 14) Tests divisibility relationship
(17, 19) Tests distinct prime numbers
(36, 48) Tests several shared factors
(81, 27) Tests repeated prime powers

Edge Cases

Both numbers are 1

When a = 1 and b = 1, the only possible common factor is 1.

A buggy implementation might incorrectly return 0 if it assumes factor searches begin at 2. This implementation correctly starts checking from 1, so the answer becomes 1.

Coprime numbers

Two numbers are coprime when their GCD is 1.

For example:

a = 17
b = 19

The only common factor is 1.

A naive implementation that misunderstands the concept of common factors might expect zero common factors. The algorithm correctly counts 1 because every positive integer shares at least the factor 1.

Equal numbers

When both numbers are identical, every factor of the number is automatically a common factor.

For example:

a = 10
b = 10

The factors are:

1, 2, 5, 10

The implementation handles this naturally because:

$\gcd(n,n)=n$

So the algorithm simply counts all divisors of the number itself.