The weight of an array is defined as the first element of the array added to the sum of absolute difference between its elements

Question

The weight of an array is defined as the first element of the array added to the sum of the absolute difference between its elements which is . For example let us consider a array a[0],a[1],a[2]...a[n] . The weight of the array given is
a[0] + |a[0]-a[1]| + |a[1]-a[2]| +|a[2]-a[3]|+ ......+|a[n-2]-a[n-1]|
You are given an array and you are asked to find average weight of all permutation of the array.

Expected Time complexity: O(Nlog(N)).

Example:
Input:
3
1 2 3
Output:
4.67
Explanation:
1 2 3 = 1 + |1-2| + |2- 3| = 3
1 3 2 = 1 + |1-3| + | 3 -2 |= 4
2 1 3 = 2 + |2-1| + | 1 -3 |= 5
3 1 2 = 3 +|3-1| + | 1 -2 |= 6
3 2 1 = 3 + |3-2| + | 2 -1 |= 5
2 3 1 = 2+ |2-3| + | 3 - 1 |=5
Weight Avg= (3 + 4 + 5+ 6 +5 +5)/6 = 4.67

Answer 1

That's not braces that's mod value of 1-2, 2-3 .....

1+|1-2| + |2-3| = 3

Answer 2

Knight_Owl_ , MoDavid
abs(1 - 2) + abs(2 - 3)
Now it makes sense ... sorry for silly question 🙏

Answer 3

Start with a factorial function, you'll need it for the average weight.
Then, get the size, dynamically allocate an array for that size, and get the elements.
I am not concerning myself with the time complexity here right now, but you can first sort the array using std::sort():

https://en.cppreference.com/w/cpp/algorithm/sort

And then repeatedly calculate the weight of the current permutation using a loop and add it to a sum variable, while generating the next permutation afterwards using std::next_permutation():

https://en.cppreference.com/w/cpp/algorithm/next_permutation

The function returns false when the first permutation has been reached again (not quite, actually, but if the array is sorted beforehand), so doing this in a do-while-loop will ensure all permutations are considered.
The last step is to divide the total weight by the amount of permutations, which is simply the factorial of the number of elements in the permutation.

Answer 4

I'm not getting how the calculation is done (bad at math, sorry)

1 + (1 - 2) + (2 - 3) => 3?
1 + -1 + -1 => ??

1 + 1 - 2 + 2 - 3 => 3?
2 - 2 + 2 - 3 => ??

Hard one indeed 😔

Answer 5

excuse me those are not braces nor mod bars... those are absolute value bars

Answer 6

😥😥 plz help