Scale Engineer

Number of Common Factors

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

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

O(min(a, b)) - The loop runs `min(a, b)` times, and each iteration involves constant time operations (modulo and comparison).

Space

O(1) - We only use a constant amount of extra space for variables like `count`, `limit`, and the loop counter `i`.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem