Rust Interview Puzzles: Find common factors

Problem

Given two positive integer numbers a and b, we need to find their common factors. A common factor of a and b is an integer number that divides both a and b without a remainder.

Examples:

Solution

fn find_common_factors(a: u32, b: u32) -> Vec<u32> {
    assert!(a > 0 && b > 0, "a & b must be positive");

    fn gcd(mut a: u32, mut b: u32) -> u32 {
        while a != b {
            if a > b {
                a = a - b;
            } else {
                b = b - a;
            }
        }
        a
    }

    (1..=gcd(a, b))
        .filter(|n| a % n == 0 && b % n == 0)
        .collect()
}

Explanation

We iterate over [1..gcd(a, b)] numbers and filter in only numbers n that divide both a and b without a remainder (a % n == 0 && b % n == 0). It is enough to iterate up to the Greatest common divisor returned by the gcd(a, b) function call.

And to calculate the gcd we use the simple Euclidean algorithm.

Complexity

The time complexity of the solution is O(gcd(a, b)). The auxiliary space complexity is O(1).

---

Rust Playground with this code