Problem

Given two positive integers a and b, return _the number ofcommon factors of _a andb.

An integer x is a common factor of a and b if x divides both a and b.

Examples

Example 1

1
2
3

Input: a = 12, b = 6
Output: 4
Explanation: The common factors of 12 and 6 are 1, 2, 3, 6.

Example 2

1
2
3

Input: a = 25, b = 30
Output: 2
Explanation: The common factors of 25 and 30 are 1, 5.

Constraints

  • 1 <= a, b <= 1000

Solution

Method 1 – Brute Force Enumeration

Intuition

The common factors of a and b are the divisors of gcd(a, b). Enumerate all numbers from 1 to min(a, b) and count those that divide both.

Approach

  1. For i from 1 to min(a, b), check if both a % i == 0 and b % i == 0.
  2. Count and return the total.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int commonFactors(int a, int b) {
        int cnt = 0;
        for (int i = 1; i <= min(a, b); ++i)
            if (a % i == 0 && b % i == 0) ++cnt;
        return cnt;
    }
};
1
2
3
4
5
6
7

func commonFactors(a, b int) int {
    cnt := 0
    for i := 1; i <= a && i <= b; i++ {
        if a%i==0 && b%i==0 { cnt++ }
    }
    return cnt
}
1
2
3
4
5
6
7
8

class Solution {
    public int commonFactors(int a, int b) {
        int cnt = 0;
        for (int i = 1; i <= Math.min(a, b); ++i)
            if (a % i == 0 && b % i == 0) cnt++;
        return cnt;
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun commonFactors(a: Int, b: Int): Int {
        var cnt = 0
        for (i in 1..minOf(a, b))
            if (a % i == 0 && b % i == 0) cnt++
        return cnt
    }
}
1
2
3

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        return sum(a%i==0 and b%i==0 for i in range(1, min(a,b)+1))
1
2
3
4
5
6
7
8
9

impl Solution {
    pub fn common_factors(a: i32, b: i32) -> i32 {
        let mut cnt = 0;
        for i in 1..=a.min(b) {
            if a%i==0 && b%i==0 { cnt += 1; }
        }
        cnt
    }
}
1
2
3
4
5
6

function commonFactors(a: number, b: number): number {
    let cnt = 0;
    for (let i = 1; i <= Math.min(a, b); ++i)
        if (a % i === 0 && b % i === 0) cnt++;
    return cnt;
}

Complexity

  • ⏰ Time complexity: O(min(a, b))
  • 🧺 Space complexity: O(1)