title: Minimum Cost to reduce the size of array to 1
body: <blockquote>
  <p>Given an array of N numbers (not necessarily sorted). We can merge any two numbers into one and the cost of merging the two numbers is equal to the sum of the two values. The task is to find the total minimum cost of merging all the numbers.</p>
  <p>Example:<br />
  Let the array A = [1,2,3,4]</p>
  <p>Then, we can remove 1 and 2, add both of them and keep the sum back in array. Cost of this step would be (1+2) = 3.</p>
  <p>Now, A = [3,3,4], Cost = 3</p>
  <p>In second step, we can 3 and 3, add both of them and keep the sum back in array. Cost of this step would be (3+3) = 6.</p>
  <p>Now, A = [4,6], Cost = 6</p>
  <p>In third step, we can remove both elements from the array and keep the sum back in array again. Cost of this step would be (4+6) = 6.</p>
  <p>Now, A = [10], Cost = 10</p>
  <p>So, total cost turns out to be 19 (10+6+3).</p>
  <p>We will have to pick the 2 smallest elements to minimize our total cost. A simple way to do this is using a min heap structure. We will be able to get the minimum element in O(1) and insertion will be O(log n).</p>
  <p>The time complexity of this approach is O(n log n).</p>
  </blockquote>
  <p>But I tried another approach, and wasn't able to find the cases where it fails. The basic idea was that the sum of two smallest elements that we will choose at any time will always be greater than the sum of the pair of elements chosen before. So the &quot;temp&quot; array will always be sorted, and we will be able to access the minimum elements in O(1).</p>
  <p>As I am sorting the input array and then simply traversing the array, the complexity of my approach is O(n log n).</p>
  <pre><code>int minCost(vector&lt;int&gt;&amp; arr) {
      sort(arr.begin(), arr.end());
      // temp array will contain the sum of all the pairs of minimum elements
      vector&lt;int&gt; temp;
      // index for arr
      int i = 0;
      // index for temp
      int j = 0;
      int cost = 0;
  
      // while we have more than 1 element combined in both the input and temp array
      while(arr.size() - i + temp.size() - j &gt; 1) {
          int num1, num2;
          // selecting num1 (minimum element)
          if(i &lt; arr.size() &amp;&amp; j &lt; temp.size()) {
              if(arr[i] &lt;= temp[j])
                  num1 = arr[i++];
              else
                  num1 = temp[j++];
          }
          else if(i &lt; arr.size())
              num1 = arr[i++];
          else if(j &lt; temp.size())
              num1 = temp[j++];
  
          // selecting num2 (second minimum element)
          if(i &lt; arr.size() &amp;&amp; j &lt; temp.size()) {
              if(arr[i] &lt;= temp[j])
                  num2 = arr[i++];
              else
                  num2 = temp[j++];
          }
          else if(i &lt; arr.size())
              num2 = arr[i++];
          else if(j &lt; temp.size())
              num2 = temp[j++];
  
          // appending the sum of the minimum elements in the temp array
          int sum = num1 + num2;
          temp.push_back(sum);
          cost += sum;
      }
      return cost;
  }
  </code></pre>
  <p>Is this approach correct? If not, please let me know what I am missing, and the test cases in which this algorithm fails.</p>
  <p><a href="https://www.spoj.com/problems/REDARR2/" rel="nofollow noreferrer">SPOJ Link for the same problem</a></p>