title: Find duplicate element in an array in O(log n) time
body: <p>I know that similar questions might be asked a number of time but it is different from those.</p>
  
  <p>Given an unsorted integer array with values <code>1 to N-1</code> has one duplicate element in it (<code>N</code> is the size of the array and max value is <code>N-1</code> because of the duplicate element). What is the best way to find the duplicate element? If possible <code>O(log n)</code>.`</p>
  
  <p>I know the <code>O(n)</code> solution but is there any way to do this problem in <code>O(log n)</code> time?</p>
  
  <p><strong>O(n) solution:</strong></p>
  
  <pre><code>1) Find sum of first N-1 natural numbers using N(N-1)/2, lets say it SUM1
  2) Find sum of all the elements of the arrays, let say it SUM2
  
  Duplicate = SUM2 - SUM1
  </code></pre>