ABSOLUTE NINJA

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
1 upvote
Asked in company
Zoho Corporation

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
4
3 5 8 9
4
5 10 15 20

Sample Output 1:

13 9 9 11
30 20 20 30

Explanation of Sample Input 1:

Test Case 1:

For this test case given array is [ 3, 5, 8, 9 ]. So you have to return [ 16, 10, 10, 12 ] as the output as :
‘13’ = [3 -3 | + | 3 - 5 | + | 3 - 8 | + | 3 - 9 | = 0 + 2 + 5 + 6
‘9’ = | 5 - 3 | + |5 - 5 | + | 5 -8 | + | 5 - 9 | = 2 + 0 + 3 + 4
‘9’ = | 8 - 3 | + | 8 -5 | + | 8 - 8 | + | 8 - 9 | = 5 + 3 + 0 + 1
‘11’ = | 9 - 3 | + | 9 -5 | + | 9 - 8 | + | 9 - 9 | = 6 + 4 + 1 + 0


Test Case 2:

For this test case given array is [ 5, 10, 15, 20 ]. So you have to return [ 30, 20, 20, 30 ] as the output as :
‘30’ = | 5 - 5 | +| 5 - 10 | + | 5 - 15 | + | 5 - 20 | = 0 + 5 + 10 + 15
‘20’ = | 10 - 5 | + | 10 - 10 | + | 10 - 15 | + | 10 - 20 | = 5 + 0 + 5 + 10
‘20’ = | 15 - 5 | + | 15 - 10 | + | 15 - 15 | + | 15 - 20 | = 10 + 5 + 0 + 5
‘30’ = | 20 - 5 | + | 20 - 10 | + | 20 - 15 | + | 20 - 20 | = 15 + 10 + 5 + 0

Sample Input 2:

2
4
1 2 3 4
4
2 4 6 8

Sample Output 2:

6 4 4 6
12 8 8 12
Hint

Can you calculate the total sum and then think of subtracting the value?

Approaches (2)
Brute Force Approach

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.
  • In the end, we return our ‘ANS’ array.
Time Complexity

O(N ^ 2), where ‘N’ is the size of the given array/list.

 

As we are iterating through each and every element through each element.

Space Complexity

O(N), where ‘N’ is the size of the given array/list.

 

As we are using an ‘ANS’ array for storing values of size ‘N’.

Code Solution
(100% EXP penalty)
ABSOLUTE NINJA
Full screen
Console