Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2427.html
2427. Number of Common Factors
- Difficulty: Easy.
- Related Topics: .
- Similar Questions: Count Primes.
Problem
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
Solution (Java, C++, Python)
-
class Solution { public int commonFactors(int a, int b) { int ans = 0, n = Math.min(a, b); for (int i = 1; i <= n; ++i) { if (a % i == 0 && b % i == 0) { ++ans; } } return ans; } } -
class Solution { public: int commonFactors(int a, int b) { int ans = 0; int n = min(a, b); for (int i = 1; i <= n; ++i) { if (a % i == 0 && b % i == 0) { ++ans; } } return ans; } }; -
class Solution: def commonFactors(self, a: int, b: int) -> int: return sum(a % i == 0 and b % i == 0 for i in range(1, 1001)) -
func commonFactors(a int, b int) int { ans := 0 for i := 1; i <= a && i <= b; i++ { if a%i == 0 && b%i == 0 { ans++ } } return ans } -
function commonFactors(a: number, b: number): number { const n = Math.min(a, b); let ans = 0; for (let i = 1; i <= n; i++) { if (a % i == 0 && b % i == 0) ans += 1; } return ans; }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).