Welcome to Subscribe On Youtube
2427. Number of Common Factors
Description
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
Solutions
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.
The time complexity is $O(\min(a, b))$, and the space complexity is $O(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.
The time complexity is $O(\sqrt{\min(a, b)})$, and the space complexity is $O(1)$.
-
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)) -
func commonFactors(a int, b int) (ans int) { g := gcd(a, b) for x := 1; x <= g; x++ { if g%x == 0 { ans++ } } return } func gcd(a int, b int) int { if b == 0 { return a } return gcd(b, a%b) } -
function commonFactors(a: number, b: number): number { const g = gcd(a, b); let ans = 0; for (let x = 1; x <= g; ++x) { if (g % x === 0) { ++ans; } } return ans; } function gcd(a: number, b: number): number { return b === 0 ? a : gcd(b, a % b); }