FindRoot | Topcoder Archive

Problem Statement

A polynomial is an expression of the form a₀x⁰ + a₁x¹ + a₂x² + ... + a_ixⁱ. A root of a polynomial is a value of x such that the the polynomial evaluates to 0. Your task is, given a int[], coeff, where the i^th element of coeff represents a_i in a polynomial, find the largest root of the polynomial. You are to return the value of this root. If the polynomial has no roots at all, return 0.

Definition

Class:: FindRoot
Method:: largest
Parameters:: int[]
Returns:: double
Method signature:: double largest(int[] coeff)
(be sure your method is public)

Notes

Your return must have relative or absolute error of less than 1e-9.

Constraints

Each element of coeff will be between -1000 and 1000, inclusive.
coeff will contain between 2 and 20 elements, inclusive.
At least one element other than element 0 will be non-zero.
If the largest root is at x, then the absolute value of the derivative of the polynomial at x will be at least 1e-6.

Examples

```
{4,-4,-1,0,1}
```
```
Returns: 1.314596212276752
```
This represents the polynomial: 4 - 4x - x2 + x4

{4,-4,-10,-2,1}

Returns: 4.420551065638042

```
{0,6,15,20,15,6,1}
```
```
Returns: 0.0
```
```
{1,0,1}
```
```
Returns: 0.0
```
x2 + 1 has not roots, so return 0.
```
{7,-35,0}
```
```
Returns: 0.2
```

{72,-39,14,-58,-15,-42,14,9,80,57}

Returns: -1.6588583311425098

{291,-198,72,-110,-326,763,286,380,-262,-359,795,424}

Returns: -0.9612593184418431

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.