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.

#2427

Easy

auto_awesome数学·结合·enumeration

LeetCode 题解工作台

公因子的数目

给你两个正整数 a 和 b ，返回 a 和 b 的公因子的数目。如果 x 可以同时整除 a 和 b ，则认为 x 是 a 和 b 的一个公因子。示例 1：输入： a = 12, b = 6 输出： 4 解释： 12 和 6 的公因子是 1、2、3、6 。示例 2：输入： a = 2…

数学枚举数论

题目描述

给你两个正整数 a 和 b ，返回 a 和 b 的公因子的数目。

如果 x 可以同时整除 a 和 b ，则认为 x 是 a 和 b 的一个 公因子 。

示例 1：

输入：a = 12, b = 6
输出：4
解释：12 和 6 的公因子是 1、2、3、6 。

示例 2：

输入：a = 25, b = 30
输出：2
解释：25 和 30 的公因子是 1、5 。

提示：

1 <= a, b <= 1000

lightbulb

解题思路

方法一：枚举

我们可以先算出 $a$ 和 $b$ 的最大公约数 $g$ ，然后枚举 $[1,..g]$ 中的每个数，判断其是否是 $g$ 的因子，如果是，则答案加一。

时间复杂度 $O(\min(a, b))$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2761 和等于目标值的质数对 #1952 三除数 #2947 统计美丽子字符串 I