0

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

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

16th Apr 2020, 7:14 AM
Ayan Biswas
Ayan Biswas - avatar
6 Respuestas
+ 2
That's not braces that's mod value of 1-2, 2-3 ..... 1+|1-2| + |2-3| = 3
16th Apr 2020, 9:19 AM
Ayan Biswas
Ayan Biswas - avatar
+ 2
Knight_Owl_ , MoDavid abs(1 - 2) + abs(2 - 3) Now it makes sense ... sorry for silly question 🙏
16th Apr 2020, 9:25 AM
Ipang
+ 2
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.
16th Apr 2020, 10:15 AM
Shadow
Shadow - avatar
+ 1
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 😔
16th Apr 2020, 8:25 AM
Ipang
+ 1
excuse me those are not braces nor mod bars... those are absolute value bars
16th Apr 2020, 9:21 AM
MoDavid
MoDavid - avatar
0
😥😥 plz help
16th Apr 2020, 8:18 AM
Ayan Biswas
Ayan Biswas - avatar