CareerCup

For simplicity assume that n = 4

Visualize the pascal triangle

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1 ignore last row because n = 4

g(x) = a x ^ 4 + b x ^ 3 + c x ^ 2 + d x + e

e = 1 * f[0] + 1 * f[1] + 1 * f[2] + 1 * f[3] + 1 * f[4] last column

d = 1 * f[1] + 2 * f[2] + 3 * f[3] + 4 * f[4] second last column

C = 1 * f[2] + 3 * f[3] + 6 * f[4] third last column

b = 1 * f[3] + 4 * f[4]

a = 1 * f[4]

This follows because

in general

if f(x) = a x ^ 2 + b x + c

g(x) = a (x+1)^2 + b ( x + 1 ) + c
= a (x^2 + 2x + 1 ) + b ( x + 1 ) + c
= a x^2 + 2 a x + a + b x + b + c
= a x^2 + ( 2a + b ) x + ( a + b + c)

and you can see that coefficents are nothing but addition of pascal columns as I have drawn above

synthetic division:

note that f(x) = g(x - 1) = (x-1)^n g[n] + ... + (x-1)g[1] + g[0]
hence we can compute the coefficients of g by iteratively dividing f by (x-1)
that is:

g_0 = f mod (x-1)
g_1 = (f div (x-1)) mod (x-1)
... and so on

one division with remainder costs O(n) ops because the degree of one polynomial is fixed
thus we have O(n^2) complexity and O(n) space

I think row wise calculation of the entire Pascal triangle of order n is better than calculating binomial coefficients using combinatrice. Although calculation of Pascal triangle requires O(n^2) space but is much more time efficient than calculating binomial coefficients (remember we will have to find factorials of a large number of numbers a number of time :-) :P)

//Using SHIFT and ADD method to construct (x+1)^i : 2<=i<= n 
//at any point of time if you have (x+1)^i, we can connstruct (x+1)^(i+1) by simple 
//shift and add. Ex. (x+1)^2 = 1 + 2^x + x^2
//to compute (x+1)^3 shift the coefficients of (x+1)^2 to the right one posiition then add to (x+1)^2. as follows
              x^0  x^1   x^2  x^3  
(x+1)^2 =     1     2     1    0
SHIFT         0     1     2    1
ADD           1     3     3    1 = (x+1)^3


using System;
using System.Collections.Generic;
using System.Text;

namespace PolynomialsProg
{
    class Program
    {
        //This function will construct (x+1)^n polynomail
        //using SHIFT and ADD method
        static void ConstructPolyDegN(int[] poly, int n)
        {
            for (int i = n-1; i >= 0; i--)
            {
                int temp = poly[i];
                poly[i] = 0;
                poly[i + 1] += temp;
                poly[i] += temp;
            }
        }
        //This function add the poly of the form factor*(x+1)^n to the result
        static void AddPolynomials(int[] result, int[] poly, int factor, int n)
        {
            for (int i = 0; i <= n; i++)            
                result[i] += factor*poly[i];
            
        }
        static void Main()
        {
            int degreeN; //the degree of the input polynomail           
            Console.Write("The degree of the polynomail: ");
            degreeN = int.Parse(Console.ReadLine());
            int[] origianlCoefficients = new int[degreeN+1];
            int[] result = new int[degreeN+1];
            int[] polynomial = new int[degreeN+1]; //will be used to construct the 
                                                   //polynomials (x+1)^i: 1<=i<=n

            //Read the input polynomail from the user 
            for (int i = 0; i <= degreeN; i++)
            {
                Console.Write("X^{0}: ", i);
                origianlCoefficients[i] = int.Parse(Console.ReadLine());
            }

            polynomial[0] = polynomial[1] = 1; //this is (x+1)
            result[0] = origianlCoefficients[0];

            for (int i = 1; i <= degreeN; i++)
            {
                if (i > 1)
                    ConstructPolyDegN(polynomial, i);

                AddPolynomials(result, polynomial, origianlCoefficients[i], i);
            }

            //Diplay the output
            for (int i = 0; i <= degreeN; i++)
                if(i == 0)
                  Console.Write("{0}+ ", result[i]);
                else
                  Console.Write("{0}X^{1} + ", result[i],i);

          


        }
    }
}

wow did Microsoft really ask this?!

Can anyone do better than O(n^2) time? I've only thought about this for 5-10 minutes, but O(n^2) time and O(n) space is the best I have so far.

Find the maximum coefficient in f(x), say M, evaluate f(M+10000) and base it by M+9999, then we know the coefficients of g(x).

def poly(coeffs):
    posCoeffs = [max(coeff, 0) for coeff in coeffs]
    negCoeffs = [max(-coeff, 0) for coeff in coeffs]
    return [i - j for i, j in zip(polyPos(posCoeffs), polyPos(negCoeffs))]

def polyPos(coeffs):
    assert all(coeff >= 0 for coeff in coeffs)
    M = max(coeffs) + 1000
    v = polyEval(coeffs, M+1)
    return base(v, M, len(coeffs))

def polyEval(coeffs, val):
    v = 0 
    for coeff in coeffs:
        v = v * val + coeff
    return v

def base(val, base, numOfCoeffs):
    # e.g. base(38, 6, 4) = [0, 1, 0, 2], 38 = 1 * 6*6 + 0 * 6 + 2 * 1
    newCoeffs = [0] * numOfCoeffs
    for i in range(numOfCoeffs):
        m = val % base
        newCoeffs[-(i+1)] = m
        val -= m
        val /= base
    return newCoeffs
    
if __name__ == "__main__":
    assert 199 == polyEval([5, 3, 1], 6)
    assert [5, 13, 9] == poly([5, 3, 1])
    assert [5, 13, 7] == poly([5, 3, -1])