Combine like terms in a polynomial equation

Question

Not homework or anything, just personal interests on coding, learning it by myself currently. Found this question interesting online.

Think if we have a list of number that's

1 2 2 4 3 6 4 2 5 4

that equals to 1x^2+2^4+3^6+4^2+5^4 How can I combine the numbers when they have the same exponent? which will become 5x^2+6x^4+3x^6

I think we can use a linked list in this case? But I don't really know use this data structure

Or anything other way to solve this kind of problem?

Prefer examples in C++ or Java

What is the maximum exponent size? If it is not too large, use an array and for a term `a x^b`, use `total[b] += a;`. With C++, a `std::map` could be used too in the same way. — Damien, Oct 09 '20 at 09:40
What are your main preferences: fast, low footprint, maintainable, or just functional? `Map` would suffice, and replace the `put` operation with `compute` to handle adding to the existing value. — BeUndead, Oct 09 '20 at 09:40

score 2 · Answer 1 · answered Oct 09 '20 at 09:45

You can do it like this:

#include <iostream>
#include <vector>
#include <map>
 
int main()
{
    std::vector<int> nums{1, 2, 2, 4, 3, 6, 4, 2, 5, 4};
    std::map<int, int> exponent_occurences;
    for (unsigned int i = 1; i < nums.size(); i += 2)
        exponent_occurences[nums.at(i)] += nums.at(i - 1);
    for (auto& [exponent, coef]: exponent_occurences)
        std::cout << coef << "x^" << exponent << std::endl;
    return 0;
}

Combine like terms in a polynomial equation

1 Answers1