algoadvance

Leetcode 2427. Number of Common Factors

Problem Statement

You are given two positive integers a and b. Return the number of common factors of a and b.

A factor of a number x is defined as an integer i where x % i == 0.

Example 1

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

Example 2

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

Clarifying Questions

  1. What are the constraints on the values of a and b?
    • Both a and b are positive integers.
  2. Could a and b be equal?
    • Yes, a and b could be equal.
  3. What is the maximum possible value for a and b?
    • The problem does not explicitly mention the maximum limits, but they are typically within a reasonable range for computation within the context of common interview problems.
  4. How should input be handled?
    • Assume the function will be called with two integer parameters, a and b.

Strategy

  1. Find the Greatest Common Divisor (GCD): The common factors of a and b are the factors of the GCD of a and b.

  2. Count factors of the GCD: Iterate through numbers from 1 to gcd(a, b), counting the numbers that divide gcd(a, b) without a remainder.

  3. Return the count: The result is the count of such divisors.

The GCD can be efficiently calculated using Euclid’s algorithm.

Code

#include <iostream>
#include <algorithm>

// Function to calculate the GCD using Euclid's algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Function to count the number of common factors
int commonFactors(int a, int b) {
    int gcdValue = gcd(a, b);
    int count = 0;

    for (int i = 1; i <= gcdValue; ++i) {
        if (gcdValue % i == 0) {
            count++;
        }
    }
    return count;
}

// Main function for testing
int main() {
    int a = 12, b = 6;
    std::cout << "Number of common factors: " << commonFactors(a, b) << std::endl;

    a = 25, b = 30;
    std::cout << "Number of common factors: " << commonFactors(a, b) << std::endl;

    return 0;
}

Time Complexity

  1. GCD Calculation: The time complexity is O(log(min(a, b))) due to Euclid’s algorithm, which efficiently calculates the GCD.
  2. Counting Factors: We iterate from 1 to gcd(a, b), which gives a time complexity of O(gcd(a, b)).

Overall Time Complexity

The overall time complexity can be approximated as O(log(min(a, b)) + gcd(a, b)). Given typical constraints, this method is efficient for computing the number of common factors for reasonable input sizes.

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