title: Find all differences in an array in O(nlogn) where n is the max range of elements
body: <p>Question: Given a sorted array A find all possible difference of elements from A, where each element is an integer in the range [1, ..., n]. Also, you can assume there are no duplicates. So max size of the array will be &lt;= n.</p>
  <p>Note: Total possible differences will be in the range of [1, ..., n-1] because of the above constraints.</p>
  <p>Example (for N=12):</p>
  <blockquote>
  <p>Input: 1, 6, 10, 12<br />
  Output: 2, 4, 5, 6, 9, 11</p>
  </blockquote>
  <p>The question is similar to <a href="https://stackoverflow.com/questions/8454573/find-all-differences-in-an-array-in-on">this one</a>, except n is the no. of elements in that question, not the upper bound of the element.</p>
  <p>There's also an answer in the same question, this one: <a href="https://stackoverflow.com/a/8455336/2109808">https://stackoverflow.com/a/8455336/2109808</a>
  This guy claims it can really be done in O(nlogn) using fft and self convolution, but I don't get it, and it also seems to be incorrect when I try it on online convolution calculators (like <a href="https://www.rapidtables.com/calc/math/convolution-calculator.html" rel="nofollow noreferrer">this one</a>).</p>
  <p>So, does anyone know how this can be achieved in O(nlogn)?</p>
  <p>Thank you in advance :)</p>