CLSR chip testing problem

    Finding ONE good VLSI chip in a population of good and bad ones, by using the
 pair test.      
        Chip A      Chip B      Conclusion  
        -------     -------     ----------  
        B is good   A is good  both are good or both are bad  
        B is good   A is bad    at least one is bad  
        B is bad    A is good   at least one is bad  
        B is bad    A is bad    at least one is bad  


    Assumption : number of goods > number of bads
    We can solve this in O(n) tim开发者_JS百科e complexity by splitting the population in half 
    every time and collecting one element of the GOOD, GOOD pair. 
     T(n) = T(n/2) + n/2
    But to collect the pairs we need n/2 memory separately. 
    Can we do this in-place without using extra memory ?? 

The algorithm is based on the question, "can we remove this chip?" So, for each chip to be removed, we simply erase it from our linked list, in place (or rather, no place at all).