algoadvance

Leetcode 2427. Number of Common Factors

Problem Statement

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 common factor of a and b is any integer that divides both a and b exactly (i.e., without leaving a remainder).

Clarifying Questions

  1. Input Constraints:
    • Are the integers a and b guaranteed to be positive?
    • What is the maximum value for a and b?
  2. Output:
    • Should the function return the count of the common factors?

Code

public class CommonFactors {
    public int commonFactors(int a, int b) {
        int gcdValue = gcd(a, b);
        int commonFactorCount = 0;
        
        // Only need to check up to gcdValue since it is the highest possible common factor
        for (int i = 1; i <= gcdValue; i++) {
            if (a % i == 0 && b % i == 0) {
                commonFactorCount++;
            }
        }
        
        return commonFactorCount;
    }

    // Helper method to calculate the Greatest Common Divisor (GCD) using Euclidean algorithm
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        CommonFactors solution = new CommonFactors();
        System.out.println(solution.commonFactors(12, 15)); // Output should be 2 (factors are 1 and 3)
        System.out.println(solution.commonFactors(100, 50)); // Output should be 6 (factors are 1, 2, 5, 10, 20, 50)
    }
}

Strategy

  1. Find the GCD: Calculate the greatest common divisor (GCD) of a and b using the Euclidean algorithm.
  2. Count Common Factors:
    • Iterate from 1 to the GCD value.
    • For each integer i in this range, check if it divides both a and b exactly.
    • Increment the count of common factors if i divides both a and b.

Time Complexity

  1. GCD Calculation:
    • The Euclidean algorithm has a time complexity of O(log(min(a, b))).
  2. Counting Factors:
    • In the worst case, we iterate up to the GCD value, making this portion O(GCD(a, b)).

Thus, the overall time complexity is O(log(min(a, b)) + GCD(a, b)).

By leveraging the GCD, we limit the range of integers we need to check, making the solution efficient for large inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI