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.

Description Hints 1 Solution Video 5:31

2427. Number of Common Factors

Easy80.6% acceptance3 companies

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

Asked at 3 companies

Google Amazon Meta

Topics

Hints open one at a time

Hint 1

For each integer in range [1,1000], check if it’s divisible by both A and B.

5:31

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution