Last Updated: 18 Apr, 2021
Sorted Transformed Output
Moderate
Asked in companies
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
Approaches
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:
- Create an array named 'ANS’ to store the final result.
- Iterate from 0 to 'N' - 1. (say, iterator = 'i'):
- ‘ANS[i]’ = QUADRATIC_EVALUATION(a, b, c, ARR[i])
- Sort ‘ANS’ in non-decreasing order.
- Return ‘ANS’.
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.
Depending on the coefficient 'A', the quadratic function is first increasing then decreasing, or first decreasing and then increasing. We will create 'ANS' to store the final result. Depending on the value of 'A' we will fill in from the left side or the right side.
The steps are as follows:
- Create an array named 'ANS' to store the final result.
- 'PT1' is the starting pointer and it is initialized to ‘0’.
- 'PT2' is the end pointer and it is initialized to ‘N' - 1.
- If 'A' > 0:
- Iterate from ‘N’ - 1 to 0. (say, iterator = 'i'):
- If 'QUADRATIC_EVALUATION' at 'PT1' is more than ‘QUADRATIC_EVALUATION’ at 'PT2' then:
- ANS[i] = ‘QUADRATIC_EVALUATION(a, b, c, arr[pt1])‘
- 'PT1' += 1
- Else:
- ‘ANS[i]’ = ‘QUADRATIC_EVALUATION(a, b, c, arr[pt2])‘
- 'PT2' -= 1
- If 'QUADRATIC_EVALUATION' at 'PT1' is more than ‘QUADRATIC_EVALUATION’ at 'PT2' then:
- Iterate from ‘N’ - 1 to 0. (say, iterator = 'i'):
- Else:
- Iterate from 0 to ‘N’ - 1. (say, iterator = 'i')
- If 'QUADRATIC_EVALUATION' at 'PT1' is less than ‘QUADRATIC_EVALUATION’ at 'PT2' then:
- ‘ANS[i]’ = ‘QUADRATIC_EVALUATION(a, b, c, arr[pt1])‘
- 'PT1' += 1
- Else:
- ‘ANS[i]’ = ‘QUADRATIC_EVALUATION(a, b, c, arr[pt2])‘
- ‘Pt2’ -= 1
- If 'QUADRATIC_EVALUATION' at 'PT1' is less than ‘QUADRATIC_EVALUATION’ at 'PT2' then:
- Iterate from 0 to ‘N’ - 1. (say, iterator = 'i')
- Return 'ANS'.
Similar problems