Last Updated: 23 Feb, 2021
Array And A Mathematics Equation
Moderate
Asked in companies
Ninja has been given a sorted array/list ‘ARR’ of integers of size ‘N’ and 3 integer coefficients ‘X’, ‘Y’, and ‘Z’. Ninja needs to sort the ‘ARR’ by applying the quadratic equation ‘X(ARR[i] * ARR[i]) + Y(ARR[i]) + Z’ to each element of ‘ARR’.
For Example :
Let ‘ARR[]’ = [1, 2, -1] and ‘X’ = 1, ’Y’ =2 and ‘Z’ = 1. Then, for each element at index ‘i’ in the ‘ARR’:
For ‘i’ = 0, ‘ARR[0]’ = 1 and after applying the equation as ‘1 * (1 * 1) + 2 * (1) + 1‘ ‘ARR[0]’ becomes 4.
For ‘i’ = 1, ‘ARR[1]’ = 2 and after applying the equation as ‘1 * (2 * 2) + 2 * (2) + 1‘ ‘ARR[1]’ becomes 9 .
For ‘i’ = 2, ‘ARR[2]’ = -1 and after applying the equation as ‘1 * (-1 * -1) + 2 * (-1) + 1‘ ‘ARR[2]’ becomes 0.
So, ‘ARR’ after modification [4, 9, 0]. The final ‘ARR’ after sorting is [0, 4, 9].
As Ninja is weak with Maths, he asks you for help. Can you help Ninja sort the given ‘ARR’ after applying the quadratic equation to each element?
Input Format :
The first line of input contains an integer ‘T’ which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains four single space-separated integers ‘N’, ’X’, ’Y’, and ‘Z’ representing the number of elements in the array/list ‘ARR’ and three coefficients of a quadratic equation.
The next line of each test case contains ‘N’ single space-separated integers denoting the elements of ‘ARR’.
Output Format :
For each test case, print the sorted ‘ARR’ after applying the given equation.
Print the output of each test case in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 100
1 <= ‘N’ <= 5000
-10^5 <= ‘X’, ‘Y’ and ‘Z’ <= 10^5
-10^5 <= ‘ARR[i]’ <= 10^5
Where 'ARR[i]' denotes the 'ith' element of the array.
Time Limit: 1 sec
Approaches
The idea behind this approach is to modify the ‘ARR’ by applying the equation on each element and then finally sort the ‘ARR’.
Here is the complete algorithm:
- Iterate the given array ‘ARR’ and for each element in the ‘ARR’ do the following:
- Apply the given equation to the element.
- Finally, sort the ‘ARR’ and return ‘ARR’.
We can optimize our solution. If we observe carefully, because this is a quadratic equation, we will always get an array/list that follows the following pattern:
- All the elements before the maximum element in the array are in increasing order.
- All the elements after the maximum element in the array are in decreasing order.
So we will iterate through the modified ‘ARR’ and find out the position of the maximum element in the ‘ARR’. Now all the elements before the maximum element will be sorted in increasing order and all the elements after that will be in decreasing order. So we will simply merge these two sub-arrays to get sorted ‘ARR’.
Here is the complete Algorithm:
- Take a variable ‘index’ to store the position of the maximum element and ‘maxElement’ to store the maximum element so far in the updated ‘ARR’ in which all the elements are modified by applying the given equation. Iterate the ‘ARR’ and for each element at index ‘i’ in the ‘ARR’ do the following:
- Apply the given equation to the element ‘ARR[i]’ and store it in the ‘ARR[i]’.
- If ‘ARR[i]’ > ‘maxElement’ then ‘maxElement’ = ‘ARR[i]’ and ‘index’ = ‘i’.
- Now, we have ‘index’ representing the position of the maximum element in the ‘ARR’.
- All the elements before ‘index’ must be sorted in increasing order.
- All the elements after ‘index’ must be sorted in decreasing order.
- We need to merge these two sub-arrays (one before the maximum element and one after the maximum element). Now, to merge these two sub-arrays in sorted increasing order, we will make a new array/list ‘temp’ having the same size as that of ‘ARR’.
- We initialise three variables ‘k’ = 0, ‘i’ = 0 and ‘j’ = ‘N’ - 1 pointing to the starting and ending element’s positions in ‘ARR’. We use ‘index’ as the breaking point of these two sub-arrays.
- Do the following while these two conditions are true ‘i’ < ‘index’ or ‘j’ > ‘index’ :
- If ‘ARR[i]’ < ‘ARR[j]’ then ‘temp[k++]’ = ‘ARR[i++]’
- Else ‘temp[k++]’ = ‘ARR[j--]’
- Do the following while ‘i’ < ‘index’
- ‘temp[k++]’ = ‘ARR[i++]’
- Do the following while ‘j’ > ‘index’
- ‘temp[k++]’ = ‘ARR[j--]’
- Finally, add the maximum element which is at ‘index’ to the ‘temp’ and return ‘temp’.
Similar problems