# Apply a funtion on sorted array

• Taken from the google interview question here

Suppose that you have a sorted array of integers (positive or negative). You want to apply a function of the form f(x) = a * x^2 + b * x + c to each element x of the array such that the resulting array is still sorted. Implement this in Java or C++. The input are the initial sorted array and the function parameters (a, b and c).

Do you think we can do it with O(n) time?

• ``````the question is rather easy, you know the f(x) is a parabolic curve,
you first need to figure out the x-axis of the highest/lowest point,
and then count number one by one from the lowest or from two end of
the array``````

• a*x^2 + b * x + c is monotonically increasing or decreasing on the two side of x_mid == -b / 2a. so if the number in the input array is all to the left or right of x_mid, the function would still remain sorted. If the number s in the input array overlap with x_mid, then starting from both end, the number with distance furthest to x_mid should be evaluated first.

a == 0 is a special case where the function become linear, and the resulting array is sorted.

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