#2427

Easy

LeetCode Problem Workspace

Number of Common Factors

The problem asks to find the number of common factors of two positive integers a and b.

Problem Statement

Given two positive integers a and b, you are tasked with returning the number of common factors between them. A common factor is an integer that divides both numbers.

To solve this, iterate through all integers from 1 to the smaller of the two numbers, checking if each one divides both a and b without leaving a remainder. Count and return the number of such factors.

Examples

Example 1

Input: a = 12, b = 6

Output: 4

The common factors of 12 and 6 are 1, 2, 3, 6.

Example 2

Input: a = 25, b = 30

Output: 2

The common factors of 25 and 30 are 1, 5.

Constraints

1 <= a, b <= 1000

Solution Approach

Brute Force Approach

The simplest approach involves checking every integer in the range [1, min(a, b)] and determining if it divides both a and b. Count how many numbers meet this condition.

Optimized Divisor Check

Instead of checking every number, calculate the divisors of a and b and then find the intersection of both sets of divisors. This approach reduces redundant checks.

Mathematical Insight with GCD

By calculating the greatest common divisor (GCD) of a and b, you can find all common divisors by iterating over the divisors of the GCD. This is a more efficient method than checking all integers.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute force approach has a time complexity of O(min(a, b)), as we are iterating through all integers up to the smaller number. The optimized approach, using divisors or GCD, can improve the time complexity to O(sqrt(min(a, b))) by reducing the range of checks.

What Interviewers Usually Probe

Looking for a straightforward brute force solution with correct divisor identification.
Candidates should mention optimization techniques such as using GCD or divisor sets.
Candidates should clearly demonstrate an understanding of how to efficiently find common factors.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check all integers up to min(a, b), potentially missing some factors.
Incorrectly assuming that a number is a common divisor without verifying divisibility by both a and b.
Overcomplicating the solution with unnecessary steps instead of using simple divisor logic.

Follow-up variants

What if the values of a and b are large, say in the range of 1,000,000?
How can this approach be adjusted to handle non-integer inputs (e.g., floating-point numbers or negative numbers)?
Can we modify this problem to find the greatest common divisor instead of counting all common divisors?

FAQ

What is the approach to solving the 'Number of Common Factors' problem?

The approach involves checking every integer from 1 to min(a, b) to see if it divides both a and b, then counting how many of these integers are common factors.

How can I optimize the brute force solution for 'Number of Common Factors'?

You can optimize the solution by using the GCD (Greatest Common Divisor) of a and b, then finding the divisors of the GCD, which will directly give you all common factors.

What is the time complexity of the brute force solution?

The time complexity of the brute force solution is O(min(a, b)) because you are checking all numbers from 1 to the smaller of a and b.

What happens if a and b are large numbers, like 1,000,000?

For large numbers, you should consider using an optimized approach, such as using GCD or finding divisors of the GCD to reduce the number of checks.

What is the difference between common factors and the greatest common divisor (GCD)?

Common factors are all integers that divide both a and b, while the GCD is the largest integer that divides both a and b. GCD can help find common factors efficiently.

terminal

Solution

Solution 1: 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.

1

2

3

4

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))

Solution 2: 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.

1

2

3

4

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))

Continue Practicing

#2761 prime pairs with target sum #1952 three divisors #2947 count beautiful substrings i