Number of Common Factors

EASY

Description

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

An integer x is a common factor of a and b if x divides both a and b.

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.

Constraints:

1 <= a, b <= 1000

Approaches

Checkout 2 different approaches to solve Number of Common Factors. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach involves iterating through all possible candidates for a common factor and checking if they divide both a and b.

Algorithm

Initialize a counter count to 0.
Determine the smaller of the two numbers, limit = min(a, b).
Loop through each integer i from 1 to limit.
Inside the loop, check if i divides both a and b without a remainder (a % i == 0 && b % i == 0).
If it does, increment the count.
After the loop finishes, return count.

The simplest way to find common factors is to test every possible candidate. A number x can only be a common factor of a and b if it divides both. This implies that x cannot be larger than a and x cannot be larger than b. Therefore, any common factor must be less than or equal to min(a, b). We can iterate through all integers i from 1 up to min(a, b). For each i, we perform a check: if (a % i == 0 && b % i == 0). If the condition is true, we've found a common factor and we increment a counter. After checking all numbers up to min(a, b), the counter will hold the total number of common factors.

class Solution {
    public int commonFactors(int a, int b) {
        int count = 0;
        int limit = Math.min(a, b);
        for (int i = 1; i <= limit; i++) {
            if (a % i == 0 && b % i == 0) {
                count++;
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(min(a, b)) - The loop runs `min(a, b)` times, and each iteration involves constant time operations (modulo and comparison).Space Complexity: O(1) - We only use a constant amount of extra space for variables like `count`, `limit`, and the loop counter `i`.

Pros and Cons

Pros:

Very simple to understand and implement.
Requires no advanced mathematical knowledge.

Cons:

Inefficient for large values of a and b, as the number of iterations is directly proportional to the smaller input number.

Code Solutions

Checking out 3 solutions in different languages for Number of Common Factors. Click on different languages to view the code.

class Solution {
public
  int commonFactors(int a, int b) {
    int g = gcd(a, b);
    int ans = 0;
    for (int x = 1; x <= g; ++x) {
      if (g % x == 0) {
        ++ans;
      }
    }
    return ans;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

Video Solution

Watch the video walkthrough for Number of Common Factors

Patterns:

MathEnumerationNumber Theory