Common factors

2427.Number of Common Factors

Math

Problem Statement:

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

Example:

Input:

a = 12, b = 6

→

Output:

4

Java Solution:

// Brute force
public int commonFactors(int a, int b) {
    int count = 0, n = 0;
    while (n++ <= Math.min(a,b)) 
        if(a % n == 0 && b % n == 0) count++;
    
    return count;
}

Python Solution:

def commonFactors(self, a: int, b: int) -> int:
    count = 0
    n = 0
    while n <= min(a, b):
        n += 1
        if a % n == 0 and b % n == 0:
            count += 1
    return count

C++ Solution:

class Solution {
public:
    int commonFactors(int a, int b) {
        int count = 0;
        int n = 0;
        while (n++ <= min(a, b)) {
            if (a % n == 0 && b % n == 0) {
                count++;
            }
        }
        return count;
    }
};

Complexity:

Time: O(min(a,b)) | Space: O(1)