title: Finding duplicate element in an array?
body: <p>I saw a interview question as follows:</p>
  
  <p>One number in array is duplicating.Find it</p>
  
  <p>Simple solution is as follows:</p>
  
  <pre><code>for(int i=0;i&lt;n;i++){
  {  
      dup = false;
      for(j=0;j&lt;n;j++){
          if(i!=j &amp;&amp; a[i]= a[j]){
              dup = true;
          }
  
         if(dup == true)
            return a[i]
       }
  }
  </code></pre>
  
  <p>But I want to implement it in O(n log(n)) and in O(n) time.  How can i do it?</p>