# Given a sorted integer array X and 3 integers A, B and C. Return the corresponding sorted polynomial array.

• Note: Time complexity should be O(n)

Apply Axx + B*x + C for each element x in the array and return the sorted array.

``````ArrayList<Integer> sortPolynomial(ArrayList<Integer> x , int a, int b, int c){
ArrayList<Integer> y1 = new ArrayList<Integer>();
ArrayList<Integer> y2 = new ArrayList<Integer>();
int prevY = a*x.get(0)*x.get(0) + b*x.get(0) + c;
for(int i=1; i<x.size(); i++) {
int curX = x.get(i);
int curY = a*curX*curX + b*curX + c;
if(curY>prevY)
else
prevY = curY;
}

// merge the sorted arrays y1 and y2
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i=y2.size() - 1; i>=0; i--)
}``````

• Suppose F(x) = Axx + B*x + C. So for sorted list of x we are required to return sorted list of F(X).

This problem can be solved using merge operation of using O(n).
Minimum value of F(x) would be where d(F(x))/dx would be zero which is x = -b/2a and graph will be symmetric about this line. As we move away from x = -b/2a F(x) will increase. so F(x1) >= F(x2) iff abs(x1 - (-b/2a)) >= abs(x2- (-b/2a)).

``````int F(vector<int> &coeff,int x)
{
return coeff[0]*x*x + coeff[1]*x + coeff[2];
}
//coeff[0]=A,coeff[1]=B,coeff[2]=C
vector<int> SortedPolynomial(vector<int> &coeff , vector<int> &X)
{
vector<int> ans;
assert(coeff[0]!=0);

double midPoint = -coeff[1]/(2*coeff[0]);
//find nearest i such that X[i] is nearest to midPoint
int i = 0;
while(i<X.size() && X[i]<midPoint)
i++;
int j = i-1;

while(i<X.size() && j>=0)
{
int next ;
if(abs(X[i]-midPoint) < abs(X[j]-midPoint))
next = X[i++];
else next = X[j--];
ans.push_back(F(coeff,next));
}
while(i<X.size())
{
ans.push_back(F(coeff,X[i]));
i++;
}
while(j>=0)
{
ans.push_back(F(coeff,X[j]));
j--;
}
// if A<0 then reverse the ans vector to make it in increasing order
if(coeff[0] < 0)
return vector<int>(ans.rbegin(),ans.rend());
return ans;
}
``````

• This post is deleted!

• All the above solutions fails for this input -
-6 -7 2 --> coeffecients array
-21 -15 12 13 14 --> sorted integer array of X

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.