Number of Common Factors

Easy
572.

Number of Common Factors

Number of Common Factors is an easy coding problem on math, enumeration and number theory, asked in Amazon and Infosys interviews.

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

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

Example 1

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

Example 2

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

Example 3

Input
a = 7, b = 13
Output
1

Constraints

  • 1 <= a, b <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var commonFactors = function(a, b) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Common Factors — Solution in Python, Java & C++

Number of Common Factors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Number of Common Factors is an easy coding problem on math, enumeration and number theory, asked in Amazon and Infosys interviews.

  • Difficulty: Easy
  • Topics: Math, Enumeration, Number Theory
  • Asked at: Amazon, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

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

Example 1

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

Example 2

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

Example 3

Input: a = 7, b = 13
Output: 1

Constraints

  • 1 <= a, b <= 1000

Hints for Number of Common Factors

  1. Hint 1

    A common factor cannot exceed the smaller of the two numbers.

  2. Hint 2

    Test every candidate from 1 up to min(a, b).

  3. Hint 3

    Equivalently, the answer is the number of divisors of gcd(a, b).

How to solve Number of Common Factors

The common factors of a and b are exactly the divisors of gcd(a, b), but with both values bounded by 1000 a direct scan is simplest.

Approach

  1. Loop d from 1 to min(a, b).
  2. Count d when it divides both a and b.

Why it works

d | a and d | b together are equivalent to d | gcd(a, b), so the scan counts precisely the divisors of the gcd — the same answer either way.

Complexity

  • Time — O(min(a, b))
  • Space — O(1)

Pitfalls

  • Looping to max(a, b) wastes work and can never find an extra factor.
  • 1 is always a common factor, so the answer is never 0.

Reference solution

Python

def commonFactors(a: int, b: int) -> int:
    return sum(1 for d in range(1, min(a, b) + 1) if a % d == 0 and b % d == 0)

Java

public static int commonFactors(int a, int b) {
    int m = Math.min(a, b);
    int count = 0;
    for (int d = 1; d <= m; d++) {
        if (a % d == 0 && b % d == 0) count++;
    }
    return count;
}

C++

int commonFactors(int a, int b) {
    int m = min(a, b);
    int count = 0;
    for (int d = 1; d <= m; d++) {
        if (a % d == 0 && b % d == 0) count++;
    }
    return count;
}

JavaScript

var commonFactors = function(a, b) {
    const m = Math.min(a, b);
    let count = 0;
    for (let d = 1; d <= m; d++) {
        if (a % d === 0 && b % d === 0) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue