Number of Common Factors - Practice Coding Problems

Number of Common Factors - 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.

Input & Output

Example 1 — Basic Case

$ Input: a = 12, b = 18

› Output: 4

💡 Note: Common factors are 1, 2, 3, and 6. Both 12 and 18 are divisible by each of these numbers.

Example 2 — Small Numbers

$ Input: a = 25, b = 30

› Output: 2

💡 Note: Common factors are 1 and 5. GCD(25,30) = 5, and 5 has factors 1 and 5.

Example 3 — Coprime Numbers

$ Input: a = 7, b = 13

› Output: 1

💡 Note: 7 and 13 are prime numbers with no common factors except 1.

Constraints

1 ≤ a, b ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Two positive integers a=12, b=18

Process

Find all numbers that divide both evenly

Output

Count of common factors: 4

Key Takeaway

🎯 Key Insight: Common factors of two numbers are exactly the factors of their GCD

Asked in

G Google 15 M Microsoft 12

The key insight is that common factors of two numbers are exactly the factors of their GCD. Best approach uses GCD + square root optimization to count factors efficiently. Time: O(log(min(a,b)) + √gcd), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(min(a, b))	O(1)	Check every number from 1 to min(a,b) to see if it divides both numbers
GCD + Square Root Optimization	O(log(min(a,b)) + sqrt(gcd))	O(1)	Find GCD first, then count its factors by checking only up to sqrt(GCD)

Brute Force — Algorithm Steps

Iterate i from 1 to min(a, b)
Check if i divides both a and b
If yes, increment counter

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin checking from i = 1

Check

Test if i divides both numbers

Count

Increment counter if it's a common factor

Code -

solution.c — C

#include <stdio.h>

int solution(int a, int b) {
    int count = 0;
    int minVal = (a < b) ? a : b;
    for (int i = 1; i <= minVal; i++) {
        if (a % i == 0 && b % i == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    int a, b;
    scanf("%d", &a);
    scanf("%d", &b);
    int result = solution(a, b);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(min(a, b))

Single loop iterates through all numbers from 1 to min(a,b)

✓ Linear Growth

Space Complexity

O(1)

Only uses a counter variable, no extra data structures

✓ Linear Space

25.0K Views

Medium Frequency

~10 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler