Number of Common Factors - Solution & Explanation

Problem Overview: Given two integers a and b, return how many integers divide both numbers without leaving a remainder. A number is a common factor if a % x == 0 and b % x == 0.

Approach 1: Direct Iteration (Time: O(min(a,b)), Space: O(1))

The straightforward solution checks every possible factor from 1 to min(a, b). For each integer i, verify whether it divides both numbers using the modulo operation. If a % i == 0 and b % i == 0, increment the count. This brute-force enumeration works because any common factor cannot exceed the smaller number. The method relies purely on enumeration and basic math operations.

This approach is easy to implement and perfectly fine for small constraints. It demonstrates clear understanding of factor checking, which interviewers often expect before discussing optimizations.

Approach 2: Using GCD (Time: O(sqrt(g)), Space: O(1))

A key observation: any number that divides both a and b must also divide g = gcd(a, b). Instead of checking all numbers up to min(a,b), compute the greatest common divisor using the Euclidean algorithm from number theory. The problem then reduces to counting how many divisors g has.

To count divisors efficiently, iterate from 1 to sqrt(g). If i divides g, then both i and g / i are valid divisors (unless they are equal). Each divisor corresponds to a number that divides both a and b. This reduces the search space significantly compared to scanning all numbers up to min(a,b).

Recommended for interviews: Start with direct iteration to show you understand what a common factor means. Then move to the GCD-based solution. Using gcd(a,b) and enumerating its divisors cuts the complexity to O(sqrt(g)), which demonstrates stronger algorithmic thinking and familiarity with number theory optimizations.