Number of Common Factors

This problem is asking us to find the common factors between two given integers, a and b. A factor of a number is an integer that can divide the number without leaving a remainder. The common factors of two numbers are the factors that both numbers have in common.

The solution involves a function that calculates the factors of a number, and then finds the common factors between a and b:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        def factors(n: int) -> set:
            """Returns a set of factors of n"""
            return set(i for i in range(1, n + 1) if n % i == 0)

        # Get the sets of factors for a and b
        factors_a = factors(a)
        factors_b = factors(b)

        # Find the intersection of the two sets, which represents the common factors
        common_factors = factors_a & factors_b

        # Return the count of common factors
        return len(common_factors)

This code defines a helper function factors that finds all factors of a given number n by looping over all integers from 1 to n and checking if n is divisible by the integer. It then finds the common factors of a and b by getting the intersection of the sets of their factors. The function returns the number of common factors.

1
2
3
4
5
6
7
8
9

from math import gcd

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        res = 1
        hi = gcd(a, b)
        for n in range(2, hi + 1):
            res += a % n == 0 and b % n == 0
        return res

This function calculates the number of common factors of two integers a and b.

Here’s how it works:

1. It starts by setting the variable res to 1. This is because 1 is a factor of every number.

2. It calculates the greatest common divisor (gcd) of a and b and assigns it to hi. The gcd is the highest number that can potentially be a common factor of a and b.

3. It then enters a loop that iterates over every number from 2 to hi (inclusive).

4. Inside the loop, it checks whether the current number n is a factor of both a and b (i.e., a and b are both divisible by n with no remainder). If so, it increments res.

5. Finally, it returns res, which is the total number of common factors of a and b.

This function has a time complexity of O(n), where n is the gcd of a and b, and a space complexity of O(1), as it only creates a constant number of variables and doesn’t use any data structures that grow with the size of the input.

1
2
3
4
5
6

int commonFactors(int a, int b) {
    int res = 1, hi = gcd(a, b);
    for (int n = 2; n <= hi; ++n)
        res += a % n == 0 && b % n == 0;
    return res;
}