Sorted Transformed Output

Posted: 18 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a quadratic function ‘Ax2 + Bx + C’ and a sorted array of 'N' integers ‘ARR’. Along with this, you are also provided with the integers ‘A’, ‘B’, and ‘C’.

Your task is to apply the given quadratic equation to each input in ‘ARR’ and return the sorted list of the outputs.

Note:

‘A’, ‘B’ and ‘C’ can be equal to 0. 
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case contains three space-separated integers ‘A’, ‘B’, and ‘C’ representing the coefficients of the quadratic equation.    

The second line of each test case will contain a single integer ‘N’ which denotes the size of the ‘ARR’. 

The third line of each test case will contain ‘N’ space-separated integers, representing the elements of ‘ARR’.
Output Format:
For each test case, return all the outputs in non-decreasing order. 

Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10^5
-10^5 <= A, B, C < =10^5
-10^5 <= ARR[ i ] <= 10^5

Time limit: 1 sec
Approach 1

We will create a helper function, to evaluate the value of the equation for a given input. 

 

long long QUADRATIC_EVALUATION(long long a, long long b, long long c, long long x)

 

It takes coefficients and the current element of ‘ARR’ as the input and returns the correspondent output.

 

We will go through all the inputs and store their ’QUADRATIC_EVALUATION’ in an array and then sort the array.

 

The steps are as follows:

 

  1. Create an array named 'ANS’ to store the final result.
  2. Iterate from 0 to 'N' - 1. (say, iterator = 'i'):
    1. ‘ANS[i]’ = QUADRATIC_EVALUATION(a, b, c, ARR[i])
  3. Sort ‘ANS’ in non-decreasing order.
  4. Return ‘ANS’.
Try Problem