Check if n-th root of product of numbers is a whole number C++

Question

I've got an assignment which sounds like this:

Given a number \$m\$ and \$n\$ other numbers, say if the \$m\$-th root of the product of those numbers is a whole number (print 1) or not (print 0). If yes, also print, in sorted order, the result of the \$m\$-th root, decomposed in prime factors.

This is how the expression would look:

$$\sqrt[m]{x_1 x_2 x_3 \dots x_n}$$

My idea was this: for the result to be a whole number, if we were to decompose all of the numbers, then make the product of all of them, every power of every base has to be divisible with \$m\$.

This is what I came up with:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

using Prime_factorization = vector < pair<int, int> >;

void add_base_and_power(Prime_factorization& prime_factorization, int    base, int power)
{
    // Check if we've already got the base we're trying to add
    auto it = find_if(prime_factorization.begin(), prime_factorization.end(), [&](pair <int, int> p) { return p.first == base; } );

    if (it != prime_factorization.end()) // If yes, add the power to the existing base
        it->second += power;
    else
        prime_factorization.push_back(make_pair(base, power)); // Else, create a new base
}

void check_if_is_factor(Prime_factorization& prime_factorization, int &number, int divisor)
{
    if (number % divisor == 0) { // If the divisor is a base, we divide until it no longer can

        int power { 0 };
        while (number % divisor == 0) {
            number /= divisor;
            ++power;
        }

        // Add base and power to factorization
        add_base_and_power(prime_factorization, divisor, power);
    }
}

void decompose(Prime_factorization& prime_factorization, int number)
{
    check_if_is_factor(prime_factorization, number, 2); // Check if it divides by 2 so after that we can only check for uneven bases


    for (int div { 3 }; div * div <= number && number > 1; div += 2)
        check_if_is_factor(prime_factorization, number, div);

    // If number is bigger than 1 it means we got out of the previous for loop with the first condition, so the number must be prime
    if (number > 1)
        add_base_and_power(prime_factorization, number, 1);
}

int main() {

    // Get m-th root
    int m;
    cin >> m;

    // Get number of terms
    int n;
    cin >> n;

    // Take n numbers and decompose each of them
    Prime_factorization prime_factorization;
    for (int i { 1 }; i <= n; ++i) {

        int x;
        cin >> x;

        decompose(prime_factorization, x);
    }

    // After decomposing all of the numbers, we check to see if each power can be divided by m(the root)
    bool okay { true };
    for (auto& i : prime_factorization)
        if (i.second % m != 0) {
            okay = false;
            break;
        }

    // We must print the base-power combinations in sorted order
    sort(prime_factorization.begin(), prime_factorization.end(), [](pair<int, int> p1, pair<int, int> p2) { return p1.first < p2.first; });

    if (okay) {
        cout << 1 << '\n';

        for (auto& i : prime_factorization)
            cout << i.first << ' ' << (i.second / m) << '\n';
    } else
        cout << 0;
}

How could I improve my code? Is there any better algorithm you might've thought of?

Answer 1

The basic approach looks sensible, but I do have a few suggestions for improvements.

using namespace std;

Bad idea. It may be a nuisance having to prepend std:: everywhere, but it's a short name in order to reduce the nuisance, and the things which could go wrong are quite bad.

---

void add_base_and_power(Prime_factorization& prime_factorization, int    base, int power)

What happened to the whitespace in int base? A single space suffices.

What do the names communicate and fail to communicate? The name prime_factorization communicates nothing: the type already says that. What purpose does this particular prime factorisation serve? The name base doesn't really fit the context IMO: you're not accumulating to a Base_power_pairs. add_prime_power(Prime_factorization accumulator, int prime, int power) would make it crystal clear what the function does.

---

void check_if_is_factor(Prime_factorization& prime_factorization, int &number, int divisor)

Again, names.

    if (number % divisor == 0) { // If the divisor is a base, we divide until it no longer can

This isn't wrong, but I wonder whether you made a conscious choice between this approach and

    int power { 0 };
    while (number % divisor == 0) {
        number /= divisor;
        ++power;
    }

    if (power > 0)
    {
        // Add base and power to factorization
        add_base_and_power(prime_factorization, divisor, power);
    }

I find the latter more aesthetically pleasing. It doesn't do a test which it knows will succeed.

NB this point is purely a subjective point about style - I'm not trying to microoptimise, and microoptimisations should be done with good benchmarks.

---

void decompose(Prime_factorization& prime_factorization, int number)

What is being decomposed here? My instinct would be that the first argument is the most relevant to interpreting the function name, but that doesn't make sense in this case.

    for (int div { 3 }; div * div <= number && number > 1; div += 2)

I've seen you use this int name { val } a few times, and (not being a C++ user) I'm not familiar with it. Does it have some advantage over int name = val to counter the disadvantage of requiring more effort to port to a different language?

There's a case to be made for calculating the square root of number outside the loop: firstly on micro-optimisation grounds, but secondly on correctness grounds. div * div could overflow the type.

---

    // We must print the base-power combinations in sorted order
    sort(prime_factorization.begin(), prime_factorization.end(), [](pair<int, int> p1, pair<int, int> p2) { return p1.first < p2.first; });

    if (okay) {
        cout << 1 << '\n';

        for (auto& i : prime_factorization)
            cout << i.first << ' ' << (i.second / m) << '\n';
    } else
        cout << 0;

Two things here: firstly, since the sorted values are only needed in one branch of the if it makes more sense to push the sort into that branch. Secondly,

if (test) {
    foo;
} else
    bar;

is easily the weirdest bracing style I've ever seen, and weird style is not good for collaboration. Do you use a company or published style guide?

---

Finally, my one algorithmic observation.

    // Check if we've already got the base we're trying to add
    auto it = find_if(prime_factorization.begin(), prime_factorization.end(), [&](pair <int, int> p) { return p.first == base; } );

    if (it != prime_factorization.end()) // If yes, add the power to the existing base
        it->second += power;
    else
        prime_factorization.push_back(make_pair(base, power)); // Else, create a new base

Linear search is never ideal. If you're using a recent standard, std::unordered_map is asymptotically preferable, and also IMO conveys the purpose better. Or maybe you would be better off with std::map, which would remove the need to sort at the end.

Answer 2

Much has already been said in @Peter Taylor answer, but it might be useful to point out a few more things. I uncommented your code and put my own comments inside it:

#include <iostream>
#include <algorithm>
#include <vector>
// using namespace std is wrong, but you know that
// already and it's common practice on code challenges sites
using namespace std;

// a space between two consecutive closing brackets isn't necessary anymore
// and has become visual clutter
using Prime_factorization = vector<pair<int, int>>; // != vector < pair<int, int> >

void add_base_and_power(Prime_factorization& prime_factorization, int base, int power)
{
    // lambda capture should be by copy if the capture is small (<= pointer size) and won't be modified inside the lambda.
    // You can also use auto for lambda arguments, which is quite useful
    auto it = find_if(prime_factorization.begin(), prime_factorization.end(), [base](const auto& p) { return p.first == base; } );
    if (it != prime_factorization.end()) 
        it->second += power;
    else
        // use emplace_back rather than push_back, it constructs the object in place
        // from the constructor's arguments
        prime_factorization.emplace_back(base, power);
}

void check_if_is_factor(Prime_factorization& prime_factorization, int &number, int divisor)
{
    if (number % divisor == 0) { 
        int power { 0 };
        // you can avoid one modulo and one comparison by using do -> while, instead of while alone
        do {
            number /= divisor;
            ++power;
        } while (number % divisor == 0);
        add_base_and_power(prime_factorization, divisor, power);
    }
}

void decompose(Prime_factorization& prime_factorization, int number)
{
    check_if_is_factor(prime_factorization, number, 2);
    for (int div { 3 }; div * div <= number && number > 1; div += 2)
        check_if_is_factor(prime_factorization, number, div);
    if (number > 1)
        add_base_and_power(prime_factorization, number, 1);
}

int main() {
    int m;
    cin >> m;
    int n;
    cin >> n;
    Prime_factorization prime_factorization;
    for (int i { 1 }; i <= n; ++i) {
        int x;
        cin >> x;
        decompose(prime_factorization, x);
    }
    // use standard algorithms whenever you can
    bool okay = std::all_of(prime_factorization.begin(), prime_factorization.end(), [m](auto p) {
        return p.second%m == 0;
    });
    // to compare with:
    /*
    bool okay { true };
    for (auto& i : prime_factorization)
        if (i.second % m != 0) {
            okay = false;
            break;
        }
    */
    // it's useless to sort prime_factorization if you don't print it
    // so you should have changed the branching order => if (!okay) cout << 0; else { sort(...); for (auto..) ...; }
    // by the way std::pair comes with an overload of operator<, so your lambda isn't necessary
    sort(prime_factorization.begin(), prime_factorization.end()); //, [](pair<int, int> p1, pair<int, int> p2) { return p1.first < p2.first; });
    if (okay) {
        cout << 1 << '\n';
        for (auto& i : prime_factorization)
            cout << i.first << ' ' << (i.second / m) << '\n';
    } else
        cout << 0;
}

About "brace initialization" -like bool okay{true}: it was meant to become the new standard but didn't, partly because of real shortcomings (it determines which constructor is called in sometimes unintuitive ways when there's an initializer-list constructor), partly because, as Peter Taylor pointed out, it isn't as readable as bool okay = true, to the point of weirdness when the initialization value is a long function call (e.g: bool ok { std::find_if(vector.begin(), vector.end(), [&capture1, capture2](auto&& element) { return ... ; }); }

Answer 3

Since you asked for a better algorithm: I would suggest a slightly different approach that will work better if you have many large prime factors, where trying to factor all the numbers might struggle. And if the input numbers are not actually an m-th power, which would be quite unlikely for random numbers, then it would be bad factoring all the numbers, only to find out that the number of factors 2 is not divisible by m, and you could have stopped much earlier. If m = 1 then your problem is effectively to factor all the numbers. So we assume m ≥ 2 and start with:

for all small primes p
    divide each x_i by p as often as possible and count the number n of factors
    if m divides n then
        remember p^{n/m} as a factor
    else
        result = NO, done

You need to decide carefully how large "small primes" may be. Anyway, you are now left with numbers that have only large prime factors. You think you need their prime factors, but you actually only need prime factors that two or more of the numbers have in common, and the GCD algorithm (greatest common divisors) finds such factors.

remove all x_i = 1
as long as there are x_i left
    calculate gcd (x_1, x_i), i ≥ 2, until a common factor g > 1 is found
    if no common factor g is found
        check if x_1 is an m-th power
        if yes then remember the prime factors 
        if not then the answer is NO, done
    else (common factor g is found)
        factor g into primes p
        for each p
             try finding m factors p, dividing numbers by factors p
             use the fact that x_1 and x_i are divisible by p
             if p^m is found then remember factor p
             else the answer is NO, done
    remove all x_i = 1

This algorithm stops when we find a prime p where the product of the number is not divisible by p^m.