Från början är denna mängd = {1..m} för alla trådar. Då kör man en rekursiv funktion som gör följande:
*Låt intervallet som funktionen kör på vara L..R och
antag att alla brytare däremellan har boolean-värdet p.
(Första gången är alltså L=1, R = m)
*Välj talet h i mitten av intervallet L..R
*Ändra alla brytare med nummer L..h till NOT p
*Testa om glödlampan lyser för varje tråd vars möjliga
lösningar är L..R. (*)
Beroende på om den lyser eller inte och på hur vi har ställt
brytarna (d.v.s. om p = true eller false) kan vi minska den tänkbara
lösningsmängden för varje tråd till antingen {L..h}
eller {h+1..R}
*Kör den rekursiva funktionen på L..h
*Kör den rekursiva funktionen på h+1..R
Lägg märke till att när vi kör den rekursiva funktionen på L..h så vet vi att alla brytare däremellan står i samma läge, antingen på eller av. Eftersom vi enligt rad (*) bara kommer att bry oss om de trådar vars möjliga lösningar ligger i detta intervall, behöver vi inte bry oss om ett dugg i vilket läge alla övriga brytare står.
Problemmakarna har varit ovanligt elaka här och lagt gränsen mycket snävt, så för att få full poäng krävs att man gör en ytterligare optimering, nämligen att man kollar om det verkligen är nödvändigt att rekursera i båda intervallen. Det kanske ändå inte är någon tråd som har den tänkbara lösningsmängden i t.ex. det lägre intervallet. Då kommer visserligen inte rad (*) att utföras, men då har vi ju ändå förlorat kommandon på att ställa om brytarna i onödan.