Factorer | Topcoder Archive

Problem Statement

A second degree polynomial ax^2 + bx + c can sometimes be factored into two first degree polynomials with integer coefficients. We want to produce the factorization as a string in the following format:

    (&lt;coef>x&lt;sign>&lt;num>)(&lt;opneg>&lt;coef>x&lt;sign>&lt;num>) 
where 
    '(' ')' and 'x' are literal 
    &lt;coef> is either empty or is a positive integer greater than 1. 
    &lt;num> is a positive integer
    &lt;sign> is a sign character, either '+' or '-'
    &lt;opneg> is an optional '-' character

Neither <coef> nor <num> can be expressed with leading zeroes.

Given a, b, and c, return the factorization as a String. If no factorization is possible, return the 4 uppercase letters "NONE". If more than one factorization is possible, choose the one with the largest coefficient of x in the first factor. If more than one is still possible, choose the one whose first factor is bigger when evaluated at x=0.

Definition

Class:: Factorer
Method:: factor
Parameters:: int, int, int
Returns:: String
Method signature:: String factor(int a, int b, int c)
(be sure your method is public)

Constraints

a, b, and c will each be between -1,000,000,000 and 1,000,000,000, inclusive.
Neither a nor c will be 0.

Examples

```
1
```
```
0
```
```
-1
```
```
Returns: "(x+1)(x-1)"
```
This factorization of x^2-1 is preferred to "(x-1)(x+1)" by the second tie breaker.
```
-4
```
```
4
```
```
-1
```
```
Returns: "(2x-1)(-2x+1)"
```
-4x^2 + 4x -1 = (2x-1)(-2x+1)
```
-4
```
```
4
```
```
5
```
```
Returns: "NONE"
```
```
1
```
```
-3
```
```
2
```
```
Returns: "(x-1)(x-2)"
```
"(x-1)(x-2)" is preferred to "(x-2)(x-1)" by the second tie-breaking rule (since -1 is greater than -2).
```
-20
```
```
0
```
```
20
```
```
Returns: "(20x+20)(-x+1)"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.