Skip to content

S2Q1 · Compute Polynomial Value

📁 GitHub
⚡ Quick Reference

Function: evaluate_polynomial(coef: list, x: int) -> int

Core idea: multiply each coefficient by the appropriate power of x and sum.

def evaluate_polynomial(coef: list, x: int) -> int:
    n = len(coef) - 1          # highest degree
    return sum(c * x ** (n - i) for i, c in enumerate(coef))

Key rules: - Coefficients are in descending degree order: coef[0] is the highest degree - coef[i] corresponds to x^(n-i) where n = len(coef) - 1 - Last element coef[-1] is the constant term (multiplied by x^0 = 1)

Problem Statement

Problem

Write a function evaluate_polynomial(coef, x) that evaluates a polynomial given its coefficients in descending order and a value for x.

For coef = [2, 3, 5, 7] the polynomial is 2x³ + 3x² + 5x + 7.

Examples:

Input 
coef=[2, 3, 5, 7], x=2
Output 
45
Input 
coef=[1, 0, -4], x=2
Output 
0
Input 
coef=[5], x=3
Output 
5

Understanding the problem

Given coef = [c₀, c₁, c₂, ..., cₙ] and degree n = len(coef) - 1:

result = c₀·xⁿ + c₁·xⁿ⁻¹ + ... + cₙ₋₁·x + cₙ

The index i maps to power n - i:

Index i Coefficient Power
0 coef[0] x^n (highest)
1 coef[1] x^(n-1)
… … …
n coef[n] x^0 = 1 (constant)

Tracing the examples

[2, 3, 5, 7] at x=2 (n=3):

i coef[i] power term
0 2 3 2 × 8 = 16
1 3 2 3 × 4 = 12
2 5 1 5 × 2 = 10
3 7 0 7 × 1 = 7

Sum = 45

[1, 0, -4] at x=2 (n=2):

i coef[i] power term
0 1 2 1 × 4 = 4
1 0 1 0 × 2 = 0
2 -4 0 -4 × 1 = -4

Sum = 0

[5] at x=3 (n=0):

i coef[i] power term
0 5 0 5 × 1 = 5

Sum = 5

Solution approaches

def evaluate_polynomial(coef: list, x: int) -> int:
    n = len(coef) - 1
    return sum(c * x ** (n - i) for i, c in enumerate(coef))

enumerate(coef) gives both index and coefficient. Power = n - i. Clean one-liner.

def evaluate_polynomial(coef: list, x: int) -> int:
    n = len(coef) - 1
    result = 0
    for i, c in enumerate(coef):
        result += c * (x ** (n - i))
    return result

Same logic written as an explicit accumulating loop -easier to trace step by step.

def evaluate_polynomial(coef: list, x: int) -> int:
    result = 0
    for c in coef:
        result = result * x + c
    return result

Horner's method rewrites ax³ + bx² + cx + d as ((ax + b)x + c)x + d. Avoids computing powers entirely -just multiply by x and add the next coefficient each step. More efficient (O(n) multiplications instead of O(n²)) and avoids floating point issues with large exponents.

Trace for [2, 3, 5, 7] at x=2: 

result = 0
c=2: result = 0*2 + 2 = 2
c=3: result = 2*2 + 3 = 7
c=5: result = 7*2 + 5 = 19
c=7: result = 19*2 + 7 = 45 


from functools import reduce

def evaluate_polynomial(coef: list, x: int) -> int:
    return reduce(lambda acc, c: acc * x + c, coef)

reduce applies Horner's method in a single functional expression -the lambda takes the accumulator and the next coefficient, multiplies by x and adds. The most compact form of Horner's method.

def evaluate_polynomial(coef: list, x: int) -> int:
    n = len(coef) - 1
    return sum(map(lambda ic: ic[1] * x ** (n - ic[0]), enumerate(coef)))

map applies a lambda to each (index, coefficient) pair from enumerate. Each call computes one term; sum adds them all. Functional alternative to the comprehension approach.

Key takeaways

01

Horner's method -the efficient approach

Rewrite the polynomial as nested multiplications: ((ax+b)x+c)x+d. No powers needed -just O(n) multiplications. The reduce(lambda acc, c: acc*x+c, coef) form is one of the most elegant uses of reduce.

02

Index to power mapping

For descending coefficients, coef[i] has power n - i where n = len(coef) - 1. This is the key formula for the direct approach.

03

Single-element list -degree 0

[5] represents the constant polynomial 5. All approaches handle this correctly: n=0, so the only term is 5 * x^0 = 5.