Factorer

TCCC07 Finals · 2007-07-30 · by dgoodman

TCCC07 Finals · 2007-07-30 · by dgoodman · Math, Search

Show categories

Class Name: Factorer

Return Type: String

Method Name: factor

Arg Types: (int, int, int)

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:

    (<coef>x<sign><num>)(<opneg><coef>x<sign><num>) 
where 
    '(' ')' and 'x' are literal 
    <coef> is either empty or is a positive integer greater than 1. 
    <num> is a positive integer
    <sign> is a sign character, either '+' or '-'
    <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.

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"

-12
0
-3
Returns: "NONE"

-12
0
3
Returns: "(6x+3)(-2x+1)"

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).

Submissions are judged against all 58 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Factorer with a public method string factor(int a, int b, int c) · 58 test cases · 2 s / 256 MB per case