Array And A Mathematics Equation

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
7 upvotes
Asked in companies
AdobeUrban Company (UrbanClap)

Problem statement

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?

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
3
2 1 1 1
1 2 
4 0 0 -1
1 2 3 4
4 0 0 0
2 4 8 9
Sample Output 1 :
3 7 
-1 -1 -1 -1 
0 0 0 0

Explanation For Sample Output 1 :

For sample test case 1: 
Given ‘X’, ‘Y’ and ‘Z’ are 1, 1 and 1 respectively. For each element at index ‘i’ in the ‘ARR’ following are the values after applying the equation:
For ‘i’ = 0, ‘ARR[0]’ = 1.After applying the equation, ‘ARR[0]’ becomes ‘1 * (1 * 1) + 1 * (1) + 1’ which is equal to 3.
For ‘i’ = 1, ‘ARR[1]’ = 2. After applying the equation, ‘ARR[1]’ becomes ‘1 * (2 * 2) + 1 * (2) + 1’ which is equal to 7.And after sorting, ‘ARR’ becomes [3,7].

For sample test case 2: 
Given ‘X’, ‘Y’ and ‘Z’ are 0, 0 and -1 respectively. For each element at index ‘i’ in the ‘ARR’ following are the values after applying the equation:
For ‘i’ = 0, ‘ARR[0]’ = 1. After applying the equation, ‘ARR[0]’ becomes ‘0 * (1 * 1) + 0 * (1) + (-1)’ which is equal to -1.
For ‘i’ = 1, ‘ARR[1]’ = 2. After applying the equation, ‘ARR[1]’ becomes ‘0 * (2 * 2) + 0 * (2) + (-1)’ which is equal to -1.
For ‘i’ = 2, ‘ARR[2]’ = 3. After applying the equation, ‘ARR[2]’ becomes ‘0 * (3 * 3) + 0 * (3) + (-1)’ which is equal to -1.
For ‘i’ = 3, ‘ARR[3]’ = 4. After applying the equation, ‘ARR[3]’ becomes ‘0 * (4 * 4) + 0 * (4) + (-1)’ which is equal to -1.And after sorting, ‘ARR’ becomes [-1,-1,-1,-1].

For sample test case 3: 
Given ‘X’, ‘Y’ and ‘Z’ are 0, 0 and 0 respectively. So every element in the ‘ARR’ becomes 0 after applying the given equation.And after sorting, ‘ARR’ becomes [0,0,0,0].
Sample Input 2 :
2
3 -1 1 -1
1 3 5 
3 1 2 1
2 3 6
Sample Output 2 :
-21 -7 -1
9 16 49

Explanation For Sample Output 2 :

For sample test case 1: 
Given ‘X’, ‘Y’ and ‘Z’ are -1, 1 and -1 respectively. For each element at index ‘i’ in the ‘ARR’ following are the values after applying the equation:
For ‘i’ = 0, ‘ARR[0]’ = 1. After applying the equation, ‘ARR[0]’ becomes ‘-1 * (1 * 1) + 1 * (1) + (-1)’ which is equal to -1.
For ‘i’ = 1, ‘ARR[1]’ = 3. After applying the equation, ‘ARR[1]’ becomes ‘-1 * (3 * 3) + 1 * (3) + (-1)’ which is equal to -7. 
For ‘i’ = 2, ‘ARR[2]’ = 5. After applying equation, ‘ARR[2]’ becomes ‘-1 * (5 * 5) + 1 * (5) + (-1)’ which is equal to -21.And after sorting, ‘ARR’ becomes [-21,-7,-1].

For sample test case 2: 
Given ‘X’, ‘Y’ and ‘Z’ are 1, 2 and 1 respectively. For each element at index ‘i’ in the ‘ARR’ following are the values after applying the equation.
For ‘i’ = 0, ‘ARR[0]’ = 2. After applying the equation, ‘ARR[0]’ becomes ‘1 * (2 * 2) + 2 * (2) + 1’ which is equal to 9.
For ‘i’ = 1, ‘ARR[1]’ = 3. After applying the equation, ‘ARR[1]’ becomes ‘1 * (3 * 3) + 2 * (3) + 1’ which is equal to 16.
For ‘i’ = 2, ‘ARR[2]’ = 6. After applying the equation ‘ARR[2]’ becomes ‘1 * (6 * 6) + 2 * (6) + 1’ which is equal to 49.And after sorting, ‘ARR’ becomes [9, 16, 49].
Hint

Think of the Brute-Force approach.

Approaches (2)
Sorting

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:

  1. Iterate the given array ‘ARR’ and for each element in the ‘ARR’ do the following:
    1. Apply the given equation to the element.
  2. Finally, sort the ‘ARR’ and return ‘ARR’.
Time Complexity

O(N log N) where ‘N’ represents the number of elements in the array 'ARR'.

 

We are iterating the ‘ARR’ only once and finally sorting the ‘ARR’ so overall time complexity will be O(N log N). 

Space Complexity

O(1) 

 

Because we are not using any extra space for finding our resultant answer.

Code Solution
(100% EXP penalty)
Array And A Mathematics Equation
Full screen
Console