Last Updated: 15 Apr, 2021
ABSOLUTE NINJA
Moderate
Asked in company
Ninja is planning a reunion with his team members. So he wants to know the sum of the absolute difference between the distances between their houses.
He collected the data and this data is given in sorted order in the form of an array/list 'POS' of size 'N'.
Your task is to find out the sum of the absolute difference between elements with each element of the given sorted array ‘POS’.
Example:
Suppose the given array is [ 2, 5, 8, 9 ]. So you have to return [ 16, 10, 10, 12 ] as the output as :
‘16’ = | 2 - 2 | + | 2 - 5 | + | 2 - 8 | + | 2 - 9 | = 0 + 3 + 6 + 7
‘10’ = | 5 - 2 | + | 5 - 5 | + | 5 - 8 | + | 5 - 9 | = 3 +0 + 3 + 4
‘10’ = | 8 - 2 | + | 8 - 5 | + | 8 - 8 | + | 8 - 9 | = 6 + 3 + 0 + 1
‘12’ = | 9 - 2 | + | 9 - 8 | + | 5 - 9 | + | 12 - 12 | = 7 + 1 + 4 + 0
Input Format:
The first line of input contains a ‘T’ number of test cases. Then next ‘T’ follows.
The first line of each test case contains an integer ‘N’ i.e size of the array ‘POS’.
The second line of each test case contains an array ‘POS’, where ‘POS[i]’ denotes the value for the ‘ith’ index.
Output Format:
For each test case, return an array containing the sum of the absolute difference of each element with each element.
Note:
You don't need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10^2
1 <= N <= 10^3
1 <= POS[i] <= 10^4
Time Limit: 1 sec
Approaches
The idea here is to use a brute approach. For each and every element, we find the absolute value and then take the sum and stored it in an array.
Suppose we have to find the answer of ‘i-th’ house then:
‘ANS[i] = ∑ abs(POS[i] - POS[j]), for every ‘j’ from ‘0’ to ‘n-1’.
- First, we declare an array/list named ‘ANS’ for storing the answer.
- Now we start iterating our ‘POS’ array and for each and every element, we go to every element and find the absolute value with each element. So we iterate two nested loops ‘i’ from the current house:
- One nested loop ‘j’ from ‘0’ to ‘N - 1’ for every house:
- ‘ANS[i] = abs ( POS[i] - POS[j])’ and stored in the sum variable in each iteration.
- One nested loop ‘j’ from ‘0’ to ‘N - 1’ for every house:
- In the end, we return our ‘ANS’ array.
The idea here is to find the total sum of the array/list and using the property of a sorted array that left side elements are smaller and larger elements lie on the right side. So, we can use this formula ( no of elements on the left side * current element - no of elements on the right side * current element ).
- First, we declare an array named ‘ANS’ for storing the answer.
- Now we store the total sum of the given array in a variable named ‘SUM’.
- Now we initialize a variable ‘TEMP’ from ‘0’.
- Now we start iterating the given array and for each element, we follow these steps:
- First, we subtract the current value ‘POS[i]’ from the ‘SUM’.
- Now add the difference of all the pairs for each element using the formula ( ‘TEMP’+ (i * POS[i]) - ((N- i - 1) * POS[i]) + ‘SUM’) to the ‘ANS’ array.
- Now we subtract the current value POS[i] from the ‘TEMP’.
- Repeat the same steps for each of the elements.
- In the end, we return the ‘ANS’ array.
Similar problems