sort the array. maintain W, the total weight of the array.
start from the smallest element and add A[i] * W to ANS.
subtract A[i] from W.
add A[i] * W again.

There is a better solution with O(1) memory and O(n) time (without sorting).

Edited by author 20.09.2020 21:51

Edited by author 20.09.2020 21:51

Do you mind sharing this solution?
I solved it using sorting but cannot think of another solution.

answer = (sum of array) ^ 2
You can get it by simple math.