title: There is an array of n numbers. One number is repeated n/2 times and other n/2 numbers are distinct
body: <p>There is an array of n numbers. One number is repeated n/2 times and other n/2 numbers are distinct.Find the repeated number. (Best soln is o(n) exactly n/2+1 comparisons.)</p>
  
  <p>the main problem here is n/2+1 comparisons.
  i have two solutions for O(n) but they are taking more than n/2+1 comparisons.</p>
  
  <p>1> divide the numbers of array in groups of three.compare those n/3 groups for any same elements.
  e.g array is (1 10 3) (4 8 1) (1 1)....so number of comparisons required is 7 which is >n/2+1
  i.e 8/2+1=5</p>
  
  <p>2> compare a[i] with a[i+1] and a[i+2] 
  e.g array is 8 10 3 4 1 1 1 1</p>
  
  <p>total 9 comparisons</p>
  
  <p>i appreciate even a little help.
  thank you</p>
  
  <p>space complexity is O(1).</p>