Sorted Transformed Output

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
1 upvote
Asked in companies
ShareChatGoogle inc

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1 2 -3 
4
-3 -1 0 1 
0 5 -3
5
-2 -1 0 1 2
Sample Output 1:
-4 -3 0 0 
-13 -8 -3 2 7
Explanation of sample input 1:
In the first test case,

graph

This figure shows all the inputs and their corresponding output. 

For the second test case, it is a line with a positive slope. So the output will increase as the input increases.
Sample Input 2:
2
0 0 11
6
-100 -88 66 68 100 211
1 0 0
5
-3 -2 0 2 3
Sample Output 2:
11 11 11 11 11 11
0 4 4 9 9
Explanation of sample input 2:
For the first test case, the given equation is a constant function y = 11. So the output will be the same for all the inputs.
Hint

Can you find the solution after calculating the value of the quadratic function for each element?

Approaches (2)
Brute force

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’.
Time Complexity

O(N* log(N)), where ‘N’ is the size of the ‘ARR’.

 

We will iterate through each element of ‘ARR’ once and compute their ’quadraticEvaluation’ and then sort all the outputs in non-decreasing order. So, the overall time complexity will be O(N * log(N)).

Space Complexity

O(N), where ‘N’ is the size of the ‘ARR’.

 

The space required to store all the output values will be O(N), So the overall space complexity will be O(N). 

Code Solution
(100% EXP penalty)
Sorted Transformed Output
Full screen
Console