title: Given an array A[], determine the minimum value of expression: min( abs( a[ i ] - x ) , abs( a[ i ] - y ) )
body: <p>Given an array A of N integers. Find two integers <code>x</code> and <code>y</code> such that the sum of the absolute difference between each array element to one of the two chosen integers is minimal.</p>
  <p>Determine the minimum value of the expression</p>
  <p><strong><code>Σ(i=0 to n) min( abs(a[i] - x), abs(a[i] - y) )</code></strong></p>
  <p>Example 1:</p>
  <ul>
  <li>N = 4</li>
  <li>A = [2,3,6,7]</li>
  </ul>
  <p><strong>Approach</strong></p>
  <ul>
  <li>You can choose the two integers, 3 and 7</li>
  <li>The required sum = |2-3| + |3-3| + |6-7| + |7-7| = 1+0+0+1 = 2</li>
  </ul>
  <p>Example 2:</p>
  <ul>
  <li>N = 8</li>
  <li>A = [ 2, 3, 5, 8, 11, 14, 17, 996 ]</li>
  </ul>
  <p><strong>Approach</strong></p>
  <ul>
  <li>You can choose the two integers, 8 and 996</li>
  <li>The required sum = |2-8| + |3-8| + |5-8| + |8-8| + |11-8| + |14-8| + |17-8| + |996-996| = 6+5+3+0+3+6+9+0 = 32</li>
  </ul>
  <p><strong>Constraints</strong></p>
  <p>1&lt;=T&lt;=100</p>
  <p>2&lt;=N&lt;=5*10^3</p>
  <p>1&lt;=A[i]&lt;=10^5</p>
  <p><em><strong>The sum of N over all test cases does not exceed 5*10^3.</strong></em></p>
  <p>**My code : **
  Please help me with the optimal solution O(N) or O(NlogN)</p>
  <pre class="lang-cpp prettyprint-override"><code>int minAbsDiff(vector&lt;int&gt; Arr, int N)
  {
          // Approach: O(N^3)
          sort(Arr.begin(), Arr.end());
          int sum = INT_MAX;
          for (int i = 0; i &lt; N; i++)
              for (int j = i + 1; j &lt; N; j++)
              {
                  int tmp_sum = 0;
                  for (int k = 0; k &lt; N; k++)
                  {
                      tmp_sum += min(abs(Arr[k] - Arr[i]), abs(Arr[k] - Arr[j]));
                  }
                  sum = min(sum, tmp_sum);
              }
          std::cout &lt;&lt; &quot;Sum is :&quot; &lt;&lt; sum &lt;&lt; std::endl;
          return sum;
  }
  </code></pre>