title: Smallest number that can not be formed from sum of numbers from array
body: <p>This problem was asked to me in Amazon interview -</p>
  
  <p>Given a array of positive integers, you have to find the smallest positive integer that can not be formed from the sum of numbers from array.</p>
  
  <p>Example:</p>
  
  <pre><code>Array:[4 13 2 3 1]
  result= 11 { Since 11 was smallest positive number which can not be formed from the given array elements }
  </code></pre>
  
  <p><br>
  What i did was :<br></p>
  
  <ol>
  <li>sorted the array</li>
  <li>calculated the prefix sum</li>
  <li>Treverse the sum array and check if next element is less than 1
  greater than sum i.e. A[j]&lt;=(sum+1). If not so then answer would
  be<b> sum+1</b></li>
  </ol>
  
  <p>But this was nlog(n) solution.<br></p>
  
  <p>Interviewer was not satisfied with this and asked a solution in less than O(n log n) time.</p>