Problem Statement
You will be given a String poly representing a polynomial in a single variable, x. poly will be represented as the sum of a number of terms of the form "ax^k", which represents x to the kth power, times a coefficient, a (which may be negative). Furthermore, each term will be separated from the next term by a single '+' and no two terms will have the same power. Thus, "5x^4+3x^1+9x^0" is an example of a valid polynomial.
Your task is to divide out all factors of the polynomial of the form "ax^1+bx^0", for integers a and b (which may be negative or 0), and return the result in the same format that it is given to you. A polynomial, A, is a factor of another polynomial, C, if there exists a polynomial, B, such that A*B=C, where all of the coefficients of A, B, and C are integers. In the returned String, you should not include any terms of the form "0x^k" and the term with the highest power should have a positive coefficient. The terms in the returned String should also be sorted in descending order by power.
For example, if given "1x^3+4x^2+4x^1+3x^0", you should remove the factor "1x^1+3x^0", to get "1x^2+1x^1+1x^0", since "1x^3+4x^2+4x^1+3x^0" is the product of "1x^1+3x^0" and "1x^2+1x^1+1x^0". "1x^2+1x^1+1x^0" has no valid factors, and so it is returned.
Definition
- Class:
- FactorPoly
- Method:
- remove
- Parameters:
- String
- Returns:
- String
- Method signature:
- String remove(String poly)
- (be sure your method is public)
Notes
- Beware of overflow!
Constraints
- poly will be a list of terms formatted as "ax^k", separated by single '+' characters, where a and k are integers.
- a in each term will not be 0, and will be between -99 and 99, inclusive, and will contain no leading '0's.
- k in each term will be between 0 and 7, inclusive, and will contain no extra leading '0's.
- poly will contain between 4 and 50 characters, inclusive.
- No two terms will have the same power (k).
Examples
"1x^3+4x^2+4x^1+3x^0"
Returns: "1x^2+1x^1+1x^0"
This is the example in the problem statement."2x^3+8x^2+8x^1+6x^0"
Returns: "1x^2+1x^1+1x^0"
This is just 2 times the previous example. Since 2 = 0x^1+2x^0, it can be factored out."2x^4+8x^3+8x^2+6x^1"
Returns: "1x^2+1x^1+1x^0"
This is just x times the previous example. Since x = 1x^1+0x^0, it can be factored out."1x^3+3x^2+3x^1+1x^0"
Returns: "1x^0"
"-2x^4+-6x^3+-6x^2+-2x^1"
Returns: "1x^0"
"2x^0+-2x^2"
Returns: "1x^0"
Notice that the terms in the input are not necessarily sorted by power (though your return must be)."1x^4+-1x^0"
Returns: "1x^2+1x^0"
"64x^7+1x^1+64x^0"
Returns: "64x^7+1x^1+64x^0"
Watch out for overflow.
Back to all problems