title: Finding defective chips between set of chips
body: <p>I am an undergrad student-computer science, and while reading some past papers I came across this question:</p>
  
  <p>I solved the question in O(n^2) like this:</p>
  
  <ol>
  <li><p>Picking randomly any chip (pivot), and connecting it with other chips (O(n))</p></li>
  <li><p>if more than of half chips state that the "pivot" is a normal chip I can simply connect it to the other chips and get the defected ones (O(n))</p></li>
  <li><p>WORST CASE: if my picked pivot is a defected chip, then I can't use it, and I will have to check (2n-1) chips, until all defected are found (O(n^2))</p></li>
  </ol>
  
  <p>Is there any better algorithm-or can anyone suggest any readings so I can get a hint?</p>