Statistics

Problem Statement for "Factorer"

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.

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

  2. -4

    4

    -1

    Returns: "(2x-1)(-2x+1)"

    -4x^2 + 4x -1 = (2x-1)(-2x+1)

  3. -4

    4

    5

    Returns: "NONE"

  4. -12

    0

    -3

    Returns: "NONE"

  5. -12

    0

    3

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

  6. -4

    0

    1

    Returns: "(2x+1)(-2x+1)"

  7. 1

    -2

    1

    Returns: "(x-1)(x-1)"

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

  9. 931170240

    931170240

    931170240

    Returns: "NONE"

  10. 931170240

    -931170240

    931170240

    Returns: "NONE"

  11. 465585120

    -931170240

    465585120

    Returns: "(465585120x-465585120)(x-1)"

  12. 1000000

    0

    -1000000

    Returns: "(1000000x+1000000)(x-1)"

  13. 1000000

    0

    -114921

    Returns: "(1000x+339)(1000x-339)"

  14. -20

    0

    20

    Returns: "(20x+20)(-x+1)"

  15. -2

    -7

    72

    Returns: "(2x-9)(-x-8)"

  16. 8

    24

    16

    Returns: "(8x+16)(x+1)"

  17. 2

    -2

    -4

    Returns: "(2x+2)(x-2)"

  18. -80

    60

    50

    Returns: "(40x-50)(-2x-1)"

  19. 2

    -9

    7

    Returns: "(2x-7)(x-1)"

  20. 2

    3

    1

    Returns: "(2x+1)(x+1)"

  21. 6

    3

    -10

    Returns: "NONE"

  22. 85

    -41

    -20

    Returns: "NONE"

  23. -73

    2

    -99

    Returns: "NONE"

  24. -940167

    -898817

    -211848

    Returns: "(12879x+5432)(-73x-39)"

  25. -449489

    -475983

    -74020

    Returns: "(19543x+3701)(-23x-20)"

  26. -59090

    -886911

    -827821

    Returns: "(59090x+827821)(-x-1)"

  27. 748436

    907312

    -484224

    Returns: "(1924x+3104)(389x-156)"

  28. 316521

    -540844

    -857365

    Returns: "(316521x-857365)(x+1)"

  29. 121524

    886681

    925016

    Returns: "(2132x+2689)(57x+344)"

  30. 624816

    -831852

    238130

    Returns: "(52068x-47626)(12x-5)"

  31. -451528

    -255803

    47655

    Returns: "(64504x-9531)(-7x-5)"

  32. 276356

    -707409

    -241542

    Returns: "(4684x-13419)(59x+18)"

  33. 670017

    -607789

    -380756

    Returns: "(223339x+95189)(3x-4)"

  34. -2363

    -970864

    20955

    Returns: "(139x-3)(-17x-6985)"

  35. 24712

    -230829

    75789

    Returns: "(24712x-8421)(x-9)"

  36. -77600

    317250

    -297999

    Returns: "(970x-2547)(-80x+117)"

  37. 235320

    515990

    254625

    Returns: "(58830x+84875)(4x+3)"

  38. 322153

    521269

    -309210

    Returns: "(24781x+51535)(13x-6)"

  39. 57684

    -203248

    -124005

    Returns: "(874x-3543)(66x+35)"

  40. 1305

    957353

    573942

    Returns: "(261x+191314)(5x+3)"

  41. -29656

    294327

    220660

    Returns: "(3707x+2596)(-8x+85)"

  42. -489199

    -435014

    788288

    Returns: "(1949x+3488)(-251x+226)"

  43. -607925

    -320370

    287555

    Returns: "(607925x-287555)(-x-1)"

  44. -233306

    -104729

    338035

    Returns: "(233306x+338035)(-x+1)"

  45. 595774

    704039

    -659148

    Returns: "(8051x-4956)(74x+133)"

  46. -138068

    35576

    173644

    Returns: "(138068x-173644)(-x-1)"

  47. -58713

    587272

    416000

    Returns: "(19571x+13000)(-3x+32)"

  48. 573420

    -233680

    -754000

    Returns: "(30180x+29000)(19x-26)"

  49. 1000000000

    1000000000

    250000000

    Returns: "(500000000x+250000000)(2x+1)"

  50. -1000000000

    -1000000000

    -250000000

    Returns: "(500000000x+250000000)(-2x-1)"

  51. 1000000000

    999999999

    250000000

    Returns: "NONE"

  52. -999999999

    -1000000000

    -250000000

    Returns: "NONE"

  53. 400000000

    40000

    4

    Returns: "NONE"

  54. -400000000

    40000

    -4

    Returns: "NONE"

  55. -4

    -40000

    -400000000

    Returns: "NONE"

  56. -100000000

    300000000

    400000000

    Returns: "(100000000x+100000000)(-x+4)"

  57. 100000000

    300000000

    -400000000

    Returns: "(100000000x+400000000)(x-1)"

  58. 100000000

    -300000000

    -400000000

    Returns: "(100000000x+100000000)(x-4)"

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.
This problem was used for: