DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Number of Common Factors - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

import math

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        
        def get_factors(num) -> set:
            res = set()
            for i in range(1, int(math.sqrt(num)) + 1):
                if num % i == 0:
                    res.add(i)
                    res.add(num // i)
            return res
        
        factors_a = get_factors(a)
        factors_b = get_factors(b)
        return len(factors_a & factors_b)

Complexity Analysis

  • Time Complexity: O(√a + √b)
  • Space Complexity: O(√a + √b)

Here, a and b are the input integers.

Mathematical Fact: All the common factors of any two numbers say a and b are exactly the factors of their GCD.

Note: Here, GCD is the Greatest Common Divisor. It is also known as the HCF or the Highest Common Factor.

  • Step 1: Calculate the GCD of a and b.
  • Step 2: Count the factors of the GCD, and return it as result.
import math

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        gcd = math.gcd(a, b)

        factors_count = 0 
        for i in range(1, int(math.sqrt(gcd)) + 1):
            if gcd % i == 0:
                factors_count += 1      # i is a factor
                if i != gcd // i:
                    factors_count += 1      # gcd // i is also a factor
        return factors_count

Complexity Analysis

  • Time Complexity: O(√gcd)
  • Space Complexity: O(√gcd)

Here, gcd is the greatest common divisor of the input integers a and b.