Number of Common Factors

Difficulty: Easy | Acceptance: 80.10% | Paid: No Topics: Math, Enumeration, Number Theory

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.

• Examples
• Constraints
• Brute Force
• Using GCD
• Optimized Divisor Counting

Examples

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

Brute Force

Intuition Check every number from 1 to the minimum of a and b, counting those that divide both numbers.

Steps

• Iterate from 1 to min(a, b)
• For each number i, check if a % i == 0 and b % i == 0
• Count such numbers

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        count = 0
        for i in range(1, min(a, b) + 1):
            if a % i == 0 and b % i == 0:
                count += 1
        return count

Complexity

• Time: O(min(a, b))
• Space: O(1)
• Notes: Simple but can be slow for large inputs

Using GCD

Intuition The common factors of a and b are exactly the divisors of their greatest common divisor (GCD).

Steps

• Compute GCD of a and b using Euclidean algorithm
• Count divisors of the GCD

import math

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

Complexity

• Time: O(gcd(a, b) + log(max(a, b)))
• Space: O(1)
• Notes: More efficient than brute force when a and b are very different

Optimized Divisor Counting

Intuition Divisors come in pairs. If i divides n, then n/i also divides n. We only need to check up to sqrt(n).

Steps

• Compute GCD of a and b
• Iterate from 1 to sqrt(gcd)
• For each divisor i, count both i and gcd/i (if different)

import math

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        gcd = math.gcd(a, b)
        count = 0
        i = 1
        while i * i <= gcd:
            if gcd % i == 0:
                if i * i == gcd:
                    count += 1
                else:
                    count += 2
            i += 1
        return count

Complexity

• Time: O(√gcd(a, b) + log(max(a, b)))
• Space: O(1)
• Notes: Most efficient approach, especially for large numbers