There are $n$ charges placed on the x-axis at points $1,2,3,\dots,n$. We need to calculate the force on each charge by every other charge. I need the exact force. Charges can be arbitrary. Inputs are the charges possibly in the form of an array. Force is defined in the usual physical way.
I know an $O(n^2)$ algorithm to do the task. However, it can be done in $O(n\log n)$.
I have read about FFT, but I don't know how to apply it here. I know that we can multiply two degree $n$ polynomials in $O(n\log n)$. This problem is similar to that problem. Any help will be appreciated.