algoadvance

Leetcode Problem 2427: Number of Common Factors

Given two positive integers a and b, return the number of common factors of a and b.

A factor of an integer n is defined as a positive integer i such that n % i == 0.

Clarifying Questions

  1. Range of Input Values: What is the range of the integers a and b?
    • If the values can be large, this could impact the choice of the algorithm.
  2. Type of Integers: Are a and b guaranteed to be positive?
    • The problem specifies they are positive integers, so no need to handle zero or negative cases.

Strategy

  1. Find the Greatest Common Divisor (GCD):
    • The number of common factors of a and b is the same as the number of factors of gcd(a, b). This simplifies the problem significantly, as finding the factors of a smaller number (the GCD) is easier.
  2. Finding All Factors of a Number:
    • Iterate through potential factors up to and including the square root of the GCD. If i is a factor, then gcd(a, b) / i is also a factor.
  3. Return the Count of Factors:
    • Count the factors found and return this count as the answer.

Time Complexity

Overall, the time complexity should be efficient for large inputs.

Code

import math
  
def common_factors(a: int, b: int) -> int:
    def gcd(x, y):
        while y:
            x, y = y, x % y
        return x
    
    def count_factors(n):
        count = 0
        for i in range(1, int(math.sqrt(n)) + 1):
            if n % i == 0:
                count += 1
                if i != n // i:
                    count += 1
        return count

    gcd_value = gcd(a, b)
    return count_factors(gcd_value)

# Example usage
print(common_factors(12, 15))  # Output: 2, because common factors are 1 and 3
print(common_factors(100, 10)) # Output: 4, because common factors are 1, 2, 5, and 10

Explanation of the Code

  1. GCD Calculation:
    • We define a helper function gcd to compute the greatest common divisor of two integers using the Euclidean algorithm.
  2. Counting Factors:
    • We define another helper function count_factors to count all the factors of a given integer n by iterating up to the square root of n and checking if each integer is a factor.
  3. Main Function:
    • Calculate the gcd of a and b.
    • Use count_factors to count the number of factors of the gcd.
    • Return the count as the result.

This solution efficiently combines GCD computation with factor counting for an optimal approach.

Try our interview co-pilot at AlgoAdvance.com