Number of Common Factors solution and explanation
Google
9 more videos on this problem
2427. Number of Common Factors | LEETCODE EASYcode Explainer · 5:31 · 919 views
2427. Number of Common Factors || In JAVA || Leetcode Problem #leetcodeQuick Learning With Sree · 4:54 · 586 views
2427. Number of Common Factors || Leetcode Contest Easy || Math || CPPCoding Techniques with Komal | Newton School · 9:03 · 561 views
Leetcode 2427. Number of Common FactorsAlgorithms Casts · 2:44 · 484 views
2427. Number of Common Factors | Leetcode | Number Theory | FundamentalsCoding with Tamilarasan · 4:57 · 402 views
2427. Number of Common Factors (Leetcode Easy)Programming Live with Larry · 1:57 · 339 views
2427. Number of Common Factors||Leetcode weekly contest313 || C++ ||Hindi ExplanationCS warriors · 1:51 · 249 views
LeetCode 2427 | Number of Common Factors | Math | JavaSleepy Cracker · 2:23 · 140 views
2427. Number of Common Factors with Python | Leetcode with Python #leetcode #youtube #pythontutorialArsalan Ahmed · 4:36 · 117 views
2427. Number of Common Factors with JavaScript | Leetcode with JavaScript #youtube #leetcode #technoArsalan Ahmed · 4:36 · 114 views
The problem
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
Approach overview
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.
Approach 1: Approach 1: Direct Iteration
In this approach, we iterate over the numbers from 1 to the minimum of the two numbers. For each number, we check if it divides both a and b. If it does, we increment the count of common factors.
This approach leverages the fact that no number larger than the smaller of a and b can be a common factor.
def common_factors(a, b):
count = 0
for i in range(1, min(a, b) + 1):
if a % i == 0 and b % i == 0:
count += 1
return count
print(common_factors(12, 6))public class CommonFactors {
public static int commonFactors(int a, int b) {
int count = 0;
for (int i = 1; i <= Math.min(a, b); i++) {
if (a % i == 0 && b % i == 0) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int a = 12, b = 6;
System.out.println(commonFactors(a, b));
}
}#include <iostream>
using namespace std;
int commonFactors(int a, int b) {
int count = 0;
for (int i = 1; i <= min(a, b); i++) {
if (a % i == 0 && b % i == 0) {
count++;
}
}
return count;
}
int main() {
int a = 12, b = 6;
cout << commonFactors(a, b) << endl;
return 0;
}function commonFactors(a, b) {
let count = 0;
for (let i = 1; i <= Math.min(a, b); i++) {
if (a % i === 0 && b % i === 0) {
count++;
}
}
return count;
}
console.log(commonFactors(12, 6));#include <stdio.h>
int commonFactors(int a, int b) {
int count = 0;
for (int i = 1; i <= ((a < b) ? a : b); i++) {
if (a % i == 0 && b % i == 0) {
count++;
}
}
return count;
}
int main() {
int a = 12, b = 6;
printf("%d\n", commonFactors(a, b));
return 0;
}using System;
class CommonFactors {
static int CommonFactors(int a, int b) {
int count = 0;
for (int i = 1; i <= Math.Min(a, b); i++) {
if (a % i == 0 && b % i == 0) {
count++;
}
}
return count;
}
static void Main() {
int a = 12, b = 6;
Console.WriteLine(CommonFactors(a, b));
}
}In the Python solution, a for loop iterates over a range from 1 to the smaller of a and b, inclusive. It checks if each number is a divisor of both a and b and counts these numbers.
Time Complexity: O(min(a, b))
Space Complexity: O(1)
Approach 2: Approach 2: Using GCD
This approach leverages the greatest common divisor (GCD) of a and b. The common factors of two numbers cannot exceed their GCD. Thus, by finding the GCD, we only need to consider the factors of the GCD as potential common factors.
Once we determine the GCD, we iterate through numbers from 1 up to this GCD to count its divisors.
import math
def common_factors(a, b):
g = math.gcd(a, b)
count = 0
for i in range(1, g + 1):
if g % i == 0:
count += 1
return count
print(common_factors(12, 6))public class CommonFactors {
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static int commonFactors(int a, int b) {
int g = gcd(a, b);
int count = 0;
for (int i = 1; i <= g; i++) {
if (g % i == 0) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int a = 12, b = 6;
System.out.println(commonFactors(a, b));
}
}#include <iostream>
using namespace std;
int gcd(int a, int b) {
while (b) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int commonFactors(int a, int b) {
int g = gcd(a, b);
int count = 0;
for (int i = 1; i <= g; i++) {
if (g % i == 0) {
count++;
}
}
return count;
}
int main() {
int a = 12, b = 6;
cout << commonFactors(a, b) << endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
function commonFactors(a, b) {
const g = gcd(a, b);
let count = 0;
for (let i = 1; i <= g; i++) {
if (g % i === 0) {
count++;
}
}
return count;
}
console.log(commonFactors(12, 6));#include <stdio.h>
int gcd(int a, int b) {
while (b) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int commonFactors(int a, int b) {
int g = gcd(a, b);
int count = 0;
for (int i = 1; i <= g; i++) {
if (g % i == 0) {
count++;
}
}
return count;
}
int main() {
int a = 12, b = 6;
printf("%d\n", commonFactors(a, b));
return 0;
}using System;
class CommonFactors {
static int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
static int CommonFactors(int a, int b) {
int g = GCD(a, b);
int count = 0;
for (int i = 1; i <= g; i++) {
if (g % i == 0) {
count++;
}
}
return count;
}
static void Main() {
int a = 12, b = 6;
Console.WriteLine(CommonFactors(a, b));
}
}This Python version uses the Python standard library to calculate the GCD and subsequently checks which numbers up to this GCD are its divisors, these being the common factors of a and b.
Time Complexity: O(log(min(a, b)) + G)
Space Complexity: O(1)
Where G is the number of divisors of the GCD.
Approach 3: Enumeration
We can first calculate the greatest common divisor g of a and b, then enumerate each number in [1,..g], check whether it is a factor of g, if it is, then increment the answer by one.
The time complexity is O(min(a, b)), and the space complexity is O(1).
function commonFactors(a: number, b: number): number {
const g = gcd(a, b);
let ans = 0;
for (let x = 1; x <= g; ++x) {
if (g % x === 0) {
++ans;
}
}
return ans;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}func commonFactors(a int, b int) (ans int) {
g := gcd(a, b)
for x := 1; x <= g; x++ {
if g%x == 0 {
ans++
}
}
return
}
func gcd(a int, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Approach 4: Optimized Enumeration
Similar to Solution 1, we can first calculate the greatest common divisor g of a and b, then enumerate all factors of the greatest common divisor g, and accumulate the answer.
The time complexity is O(\sqrt{min(a, b)}), and the space complexity is O(1).
function commonFactors(a: number, b: number): number {
const g = gcd(a, b);
let ans = 0;
for (let x = 1; x * x <= g; ++x) {
if (g % x === 0) {
++ans;
if (x * x < g) {
++ans;
}
}
}
return ans;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}func commonFactors(a int, b int) (ans int) {
g := gcd(a, b)
for x := 1; x*x <= g; x++ {
if g%x == 0 {
ans++
if x*x < g {
ans++
}
}
}
return
}
func gcd(a int, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Direct Iteration | Time Complexity: O(min(a, b)) |
| Approach 2: Using GCD | Time Complexity: O(log(min(a, b)) + G) Where G is the number of divisors of the GCD. |
| Enumeration | – |
| Optimized Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Iteration | O(min(a,b)) | O(1) | Simple implementation when numbers are small or constraints are low |
| Using GCD + Divisor Enumeration | O(sqrt(g)) | O(1) | Preferred optimized approach when numbers are larger and divisor counting is faster |
Frequently asked questions
Is Number of Common Factors easy or hard?
Number of Common Factors is classified as an Easy problem. It focuses on basic divisor checks and understanding the relationship between common factors and the greatest common divisor.
Number of Common Factors Python/Java solution
Python and Java implementations usually compute gcd(a, b) first, then loop from 1 to sqrt(g) to count divisors. This keeps the runtime around O(sqrt(g)) and uses constant extra space.
How to solve Number of Common Factors in O(sqrt(n))?
First compute g = gcd(a, b) using the Euclidean algorithm. Then iterate from 1 to sqrt(g) and check which numbers divide g. Each divisor pair (i and g/i) represents valid common factors of both numbers.
What is the best approach for Number of Common Factors?
The most efficient approach computes gcd(a, b) and counts the divisors of that GCD. Any common factor of a and b must divide their greatest common divisor. Enumerating divisors up to sqrt(g) gives O(sqrt(g)) time and O(1) space complexity.
Is Number of Common Factors asked at Google/Amazon/Meta?
This exact problem is typically categorized as an easy math and number theory question. Similar factor-counting and GCD-based problems appear in interviews at companies like Amazon and Google when testing basic mathematical reasoning.
What data structure is used in Number of Common Factors?
No specialized data structure is required. The problem relies on arithmetic operations, the Euclidean algorithm for GCD, and divisor enumeration using simple loops.
What is the time complexity of Number of Common Factors?
The brute force solution runs in O(min(a,b)) time because it checks every integer up to the smaller value. The optimized approach computes gcd(a,b) and counts its divisors in O(sqrt(g)) time, where g is the GCD.