2427. Number of Common Factors

EasyMathEnumerationNumber Theory

Problem Description

In this problem, you are given two positive integers, a and b. Your task is to find out how many common factors these two numbers share. A common factor is defined as an integer x that can divide both a and b without leaving a remainder. This is straightforward in the sense that all you need to do is count all numbers from 1 to the smallest of a and b, checking if they are factors of both.

Intuition

To efficiently solve this problem, we leverage the fact that the common factors of a and b must also be factors of the greatest common divisor (gcd) of a and b. The greatest common divisor of two numbers is the largest number that divides both of them without leaving a remainder. Once we find the gcd of a and b, we just need to count the number of factors this gcd has because they will naturally be common factors of both a and b.

The steps to arrive at this solution are:

Calculate the gcd of a and b, using the gcd function (which is presumably imported from the [math](/problems/math-basics) module, although it is not shown in the code). The gcd represents the largest common factor of both numbers.
Initialize two variables; ans to keep the count of common factors found, and x to iterate through possible factors, starting at 1.
Use a while loop to check every integer smaller or equal to the square root of gcd (x * x <= g). We perform this check only until the square root because if x is a factor of g, there will be a corresponding factor g / x which is either equal to x (when x*x == g) or greater than x (when x is less than the square root of g).
Within the loop, if x divides g without a remainder (g % x == 0), it means x is a factor. Thus, we increase ans by 1. We also check if x * x is strictly less than g, which suggests there is another factor at the other side of the square root of g. If so, we increase ans by another 1.
Increment x by 1 to check the next integer.
After finishing the loop, we return ans, which is the total count of the common factors.

This method is significantly faster than checking each number from 1 to min(a, b). Instead, it only checks up to the square root of the gcd, which is an optimization based on the property that if x is a factor of y, then y must have another factor that is either y / x or x itself.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

In solving this problem, the algorithm follows a series of logical steps based on number theory. There's reliance on a core mathematical concept—every number has a unique factorization and can be represented as the product of their prime factors raised to various powers. Extending this, the common factors of two numbers will be associated with the common prime factors of those numbers. Therefore, calculating the greatest common divisor (gcd) of the two numbers gives us a number that has all and only the prime factors shared between the two.

The code structure:

First, we find the gcd of the two given numbers, a and b, using a gcd function. The gcd(a, b) in the code represents this highest common factor and is stored in variable g.
We then initialize two variables: ans to 0, which will serve as a counter for the common factors, and x to 1, to iterate through potential factors starting from 1 up to the square root of g.
The code uses a while loop to iterate through all the numbers from 1 up until the square root of the gcd. The condition x * x <= g guarantees that we do not check past the square root, maximizing efficiency.
Inside the loop, the modulo operation g % x checks if x divides g with no remainder—if it does, x is a factor of g. Since g is the gcd of a and b, x is also a common factor of a and b. So, we increment ans by 1.
We also look for the factor pair of x, which is g / x. If x * x is less than g, then g / x is another factor of g that is distinct from x. Therefore, we have another factor to add to our ans count, so we increment ans by 1 again.
After evaluating a potential factor x, we increment x by 1 to check the next number. This continues until x exceeds the square root of g.
Lastly, we return ans, which now contains the count of all the unique common factors of a and b.

No complex data structures are needed for this approach; simple integer variables suffice for the implementation. The pattern applied here is the efficient detection of factors via examining up to the square root, which is a widely-adopted practice in algorithms involving factorization or prime numbers, owing to its computational efficiency.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Example Walkthrough

Let's say you are given a = 8 and b = 12 and you want to find the common factors. According to the aforementioned approach, here is a step-by-step process to compute the answer:

Calculate the gcd: We start by calculating the greatest common divisor of 8 and 12. The gcd of 8 and 12 is 4, as 4 is the largest number that can divide both 8 and 12 without leaving a remainder.
Initialize variables: We initialize ans to 0 to count the number of common factors. We also initialize x to 1 to start checking possible factors from 1.
Loop through potential factors: We use a while loop to check for factors starting from x = 1. Since the gcd is 4, we only need to check for factors up to the square root of 4, which is 2.
Check divisibility: During the first iteration with x = 1, we find that 4 % 1 == 0. Therefore, 1 is a factor of 4, and we increment ans to 1.
Find factor pairs: We then check if 1 has a factor pair distinct from itself by confirming that 1 * 1 < 4. Since this is not the case (1*1 == 1), we do not increment ans.
Increment and check next potential factor: We increment x to 2 and perform the check again. We find that 4 % 2 == 0, so 2 is a factor and ans becomes 2.
No other factors to check: There aren't any numbers between 2 and the square root of 4 (which is 2), so we stop the loop here. There is no need to increment ans further, as 2 * 2 == 4 which does not suggest that there is another correspondent factor besides 2.
Return the count: The variable ans contains the count of common factors, which in this case is 2. Hence, 8 and 12 have 2 common factors: 1 and 2.

Both 1 and 2 are common factors because both numbers can be divided by these factors without a remainder. So the result for the input a = 8 and b = 12 would be 2.

This example fits into the solution approach as a straightforward instance of the general method, illustrating the reasoning and calculations behind finding common factors of two numbers by means of their greatest common divisor.

Solution Implementation

1from math import gcd
2
3class Solution:
4    def commonFactors(self, a: int, b: int) -> int:
5        # Calculate the greatest common divisor (GCD) of a and b
6        greatest_common_divisor = gcd(a, b)
7        # Initialize answer as 0 (will count common factors)
8        number_of_common_factors = 0
9        # Start with potential factor 1
10        potential_factor = 1
11      
12        # Check all numbers up to and including the square root of the GCD
13        while potential_factor * potential_factor <= greatest_common_divisor:
14            # If potential_factor is a factor of the GCD
15            if greatest_common_divisor % potential_factor == 0:
16                # Increment count due to one factor found
17                number_of_common_factors += 1
18                # If it is not a perfect square, count the corresponding
19                # larger factor (greatest_common_divisor // potential_factor)
20                if potential_factor * potential_factor < greatest_common_divisor:
21                    number_of_common_factors += 1
22            # Move to the next potential factor
23            potential_factor += 1
24
25        # Return the total count of common factors
26        return number_of_common_factors
27

1class Solution {
2    // Function to calculate the number of common factors of numbers a and b
3    public int commonFactors(int a, int b) {
4        // Calculate the Greatest Common Divisor (GCD) of a and b
5        int gcdValue = gcd(a, b);
6        int count = 0; // Initialize a counter for the number of common factors
7
8        // Iterate through all numbers from 1 to the square root of the gcdValue
9        for (int x = 1; x * x <= gcdValue; ++x) {
10            // Check if x is a divisor of gcdValue
11            if (gcdValue % x == 0) {
12                ++count; // Increment the count for the divisor x
13
14                // If x is not the square root of gcdValue, increment the count for the quotient as well
15                if (x * x < gcdValue) {
16                    ++count; // Increment the count for the divisor gcdValue / x
17                }
18            }
19        }
20        return count; // Return the total count of common factors
21    }
22
23    // Helper function to calculate the GCD of a and b using Euclid's algorithm
24    private int gcd(int a, int b) {
25        // If b is 0, a is the GCD
26        return b == 0 ? a : gcd(b, a % b);
27    }
28}
29

1#include <algorithm> // include the algorithm header for std::gcd
2
3class Solution {
4public:
5    // Function to find the number of common factors of two numbers
6    int commonFactors(int a, int b) {
7        // std::gcd is a library function to find the greatest common divisor of a and b
8        int greatestCommonDivisor = std::gcd(a, b);
9        int commonFactorCount = 0; // Initialize the count of common factors
10      
11        // Loop through all numbers from 1 to greatestCommonDivisor
12        for (int divisor = 1; divisor <= greatestCommonDivisor; ++divisor) {
13            // Increase the count if divisor is a factor of greatestCommonDivisor
14            if (greatestCommonDivisor % divisor == 0) {
15                commonFactorCount++;
16            }
17        }
18      
19        // Return the total count of common factors
20        return commonFactorCount;
21    }
22};
23

1// Function to count all common factors of two numbers
2function commonFactors(a: number, b: number): number {
3    // Calculate the greatest common divisor (GCD) of a and b
4    const greatestCommonDivisor = gcd(a, b);
5    let commonFactorCount = 0;
6
7    // Loop through each number from 1 up to the square root of the GCD
8    for (let divisor = 1; divisor * divisor <= greatestCommonDivisor; ++divisor) {
9        // If the divisor is a factor of GCD
10        if (greatestCommonDivisor % divisor === 0) {
11            // Count the divisor as a common factor
12            ++commonFactorCount;
13            // If the divisor is not the square root of GCD, count the complementary factor
14            if (divisor * divisor < greatestCommonDivisor) {
15                ++commonFactorCount;
16            }
17        }
18    }
19    // Return the total count of common factors
20    return commonFactorCount;
21}
22
23// Function to calculate the greatest common divisor (GCD) of two numbers using Euclid's algorithm
24function gcd(a: number, b: number): number {
25    // If second number is zero, the GCD is the first number
26    return b === 0 ? a : gcd(b, a % b);
27}
28

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]["jm", "kn", "lo"]["jklmnp"]["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down into two parts: computing the greatest common divisor (GCD) of a and b, and finding the common factors based on the GCD.

The first line in the function makes a call to gcd(a, b). The GCD of two numbers a and b is typically computed using the Euclidean algorithm, which has a time complexity of O(log(min(a, b))).
The while loop runs as long as x * x <= g, which means it runs approximately sqrt(g) times where g is the GCD of a and b. In each iteration, the loop performs a constant amount of work, so the loop contributes O(sqrt(g)) to the time complexity.

Combining these parts, the total time complexity of the given code is O(log(min(a, b)) + sqrt(g)), where g is the GCD of a and b.

Space Complexity

The space complexity of the code is determined by the amount of extra space used aside from input storage. Since no additional data structures are utilized that grow with the size of the input, and only a fixed number of integer variables are used (g, ans, x), the space complexity of the code is O(1), which refers to constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these properties could exist for a graph but not a tree?

Contain cyclesThere are multiple ways to traverseConnectedHas no cycle

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2427. Number of Common Factors

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings