Jobs

Interviews

Discussions

Number of Common Factors

Easy

Asked by:

55 views

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

Try coding it in LeetCode

Number of Common Factors

Easy

Asked by:

55 views

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the two input numbers?
Will the inputs ever be zero or negative?
Are the inputs guaranteed to be integers?
What should be returned if there are no common factors other than 1?
Do you expect a particularly optimized solution, or is a more straightforward approach sufficient?

Brute Force Solution

Approach

The brute force approach to finding the number of common factors involves checking every possible number to see if it divides both input numbers. It is simple to understand and implement. We are essentially testing all possibilities between 1 and the smaller of the two numbers.

Here's how the algorithm would work step-by-step:

Start with the number 1.
Check if number 1 divides both the first and second input numbers without leaving a remainder.
If it does, count it as a common factor.
Move on to the next number, which is 2.
Check if number 2 divides both the first and second input numbers without leaving a remainder.
If it does, count it as a common factor.
Continue doing this for every whole number, one at a time.
Stop when you reach the smaller of the two input numbers.
The total number of common factors you've counted is your final answer.

Code Implementation

def number_of_common_factors_brute_force(number1, number2):    number_of_common_factors = 0
    smaller_number = min(number1, number2)

    for possible_factor in range(1, smaller_number + 1):
        # Need to check if the number is a factor of both input numbers
        if number1 % possible_factor == 0:

            if number2 % possible_factor == 0:
                # Found a common factor, so increment the count
                number_of_common_factors += 1

    return number_of_common_factors

Big(O) Analysis

Time Complexity

O(min(a, b)) – The algorithm iterates from 1 up to the smaller of the two input numbers, 'a' and 'b'. In each iteration, it performs a constant number of operations (division and comparison) to check if the current number is a factor of both 'a' and 'b'. Therefore, the number of iterations is bounded by min(a, b), which directly determines the execution time. This leads to a time complexity of O(min(a, b)).

Space Complexity

O(1) – The brute force approach described only uses a few integer variables: the current number being checked (from 1 up to the smaller input number) and a counter for the common factors. The number of integer variables does not depend on the input numbers. Therefore, the auxiliary space required remains constant, regardless of the size of the input.

Optimal Solution

Approach

The most efficient way to find the number of common factors is to realize that any common factor must also be a factor of the smaller number. We can iterate through possible factors up to the smaller number and only check if they divide both numbers evenly.

Here's how the algorithm would work step-by-step:

First, find the smaller of the two numbers.
Then, start checking numbers from 1 up to the smaller number to see if they are factors of both numbers.
For each number you check, determine if it divides evenly into both numbers. If it does, that number is a common factor.
Keep a running count of the common factors you find.
After checking all numbers up to the smaller number, the count you have is the total number of common factors.

Code Implementation

def number_of_common_factors(number_1, number_2):
    smaller_number = min(number_1, number_2)
    common_factor_count = 0

    # Iterate from 1 to the smaller number to find potential factors.
    for possible_factor in range(1, smaller_number + 1):
        # Check if the possible factor divides both numbers evenly.
        if number_1 % possible_factor == 0:

            if number_2 % possible_factor == 0:
                # Increment the count if it's a common factor.
                common_factor_count += 1

    return common_factor_count

Big(O) Analysis

Time Complexity

O(min(a, b)) – The algorithm's runtime is primarily determined by the loop that iterates from 1 up to the smaller of the two input numbers, 'a' and 'b'. The input size can be considered min(a, b), because the loop executes a number of times proportional to its value. Inside the loop, a constant amount of work is done to check if the current number is a factor of both 'a' and 'b'. Therefore, the time complexity is directly proportional to min(a, b), resulting in O(min(a, b)).

Space Complexity

O(1) – The algorithm uses a single variable to store the smaller of the two input numbers, and another variable to count the number of common factors. Regardless of the input values, only these two integer variables are needed, thus the algorithm uses constant extra space. No additional data structures or recursion are involved. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Either input number is zero	Return 0 as 0 has infinite factors and the only common factor with 0 is the other number when it is also 0.
Both input numbers are 1	Return 1, as 1 is the only common factor.
One input number is very large (close to the maximum integer value)	Ensure the algorithm doesn't lead to integer overflow when calculating factors; use long or appropriate data types.
Both input numbers are the same large number	The number of common factors will be equal to the number of factors of that single number, calculated without overflow.
One number is a multiple of the other (e.g., 12 and 4)	The common factors will be all factors of the smaller number.
Both numbers are prime numbers	Return 1, as the only common factor is 1.
Both numbers are negative	Take the absolute value of both numbers, as factors are generally considered positive.
One number is negative and one is positive	Take the absolute value of both numbers, as factors are generally considered positive.

Either input number is zero

How to Handle:

Return 0 as 0 has infinite factors and the only common factor with 0 is the other number when it is also 0.

Both input numbers are 1

How to Handle:

Return 1, as 1 is the only common factor.

One input number is very large (close to the maximum integer value)

How to Handle:

Ensure the algorithm doesn't lead to integer overflow when calculating factors; use long or appropriate data types.

Both input numbers are the same large number

How to Handle:

The number of common factors will be equal to the number of factors of that single number, calculated without overflow.

One number is a multiple of the other (e.g., 12 and 4)

How to Handle:

The common factors will be all factors of the smaller number.

Both numbers are prime numbers

How to Handle:

Return 1, as the only common factor is 1.

Both numbers are negative

How to Handle:

Take the absolute value of both numbers, as factors are generally considered positive.

One number is negative and one is positive

How to Handle:

Take the absolute value of both numbers, as factors are generally considered positive.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the two input numbers?
Will the inputs ever be zero or negative?
Are the inputs guaranteed to be integers?
What should be returned if there are no common factors other than 1?
Do you expect a particularly optimized solution, or is a more straightforward approach sufficient?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number 1.
Check if number 1 divides both the first and second input numbers without leaving a remainder.
If it does, count it as a common factor.
Move on to the next number, which is 2.
Check if number 2 divides both the first and second input numbers without leaving a remainder.
If it does, count it as a common factor.
Continue doing this for every whole number, one at a time.
Stop when you reach the smaller of the two input numbers.
The total number of common factors you've counted is your final answer.

Code Implementation

def number_of_common_factors_brute_force(number1, number2):    number_of_common_factors = 0
    smaller_number = min(number1, number2)

    for possible_factor in range(1, smaller_number + 1):
        # Need to check if the number is a factor of both input numbers
        if number1 % possible_factor == 0:

            if number2 % possible_factor == 0:
                # Found a common factor, so increment the count
                number_of_common_factors += 1

    return number_of_common_factors

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the smaller of the two numbers.
Then, start checking numbers from 1 up to the smaller number to see if they are factors of both numbers.
For each number you check, determine if it divides evenly into both numbers. If it does, that number is a common factor.
Keep a running count of the common factors you find.
After checking all numbers up to the smaller number, the count you have is the total number of common factors.

Code Implementation

def number_of_common_factors(number_1, number_2):
    smaller_number = min(number_1, number_2)
    common_factor_count = 0

    # Iterate from 1 to the smaller number to find potential factors.
    for possible_factor in range(1, smaller_number + 1):
        # Check if the possible factor divides both numbers evenly.
        if number_1 % possible_factor == 0:

            if number_2 % possible_factor == 0:
                # Increment the count if it's a common factor.
                common_factor_count += 1

    return common_factor_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Either input number is zero	Return 0 as 0 has infinite factors and the only common factor with 0 is the other number when it is also 0.
Both input numbers are 1	Return 1, as 1 is the only common factor.
One input number is very large (close to the maximum integer value)	Ensure the algorithm doesn't lead to integer overflow when calculating factors; use long or appropriate data types.
Both input numbers are the same large number	The number of common factors will be equal to the number of factors of that single number, calculated without overflow.
One number is a multiple of the other (e.g., 12 and 4)	The common factors will be all factors of the smaller number.
Both numbers are prime numbers	Return 1, as the only common factor is 1.
Both numbers are negative	Take the absolute value of both numbers, as factors are generally considered positive.
One number is negative and one is positive	Take the absolute value of both numbers, as factors are generally considered positive.

Either input number is zero

How to Handle:

Return 0 as 0 has infinite factors and the only common factor with 0 is the other number when it is also 0.

Both input numbers are 1

How to Handle:

Return 1, as 1 is the only common factor.

One input number is very large (close to the maximum integer value)

How to Handle:

Ensure the algorithm doesn't lead to integer overflow when calculating factors; use long or appropriate data types.

Both input numbers are the same large number

How to Handle:

The number of common factors will be equal to the number of factors of that single number, calculated without overflow.

One number is a multiple of the other (e.g., 12 and 4)

How to Handle:

The common factors will be all factors of the smaller number.

Both numbers are prime numbers

How to Handle:

Return 1, as the only common factor is 1.

Both numbers are negative

How to Handle:

Take the absolute value of both numbers, as factors are generally considered positive.

One number is negative and one is positive

How to Handle:

Take the absolute value of both numbers, as factors are generally considered positive.