Wires And Switches You are given a black box that connects n wires to n switches
ID: 3596618 • Letter: W
Question
Wires And Switches You are given a black box that connects n wires to n switches. Each wire is connected to exactly one switch. Each switch is connected to zero or more wires. Your goal is to determine which wire is connected to each switch, without opening the box. You can perform a sequence of the following two operations: (1) Turn some switch j on or off. (2) Test some wire i. When testing a wire, if the switch it is connected to is on, then a lamp lights up. Wires Switches It is easy to discover all the connections using 0(n2) operations, as follows Initially, turn all the switches off (n operations) for i=l to n do for j = 1 to n do Turn switch j on Test wire i if the lamp lights up then we know that the wire i is connected to switch j Turn switch j off Give an algorithm which discovers all the connections using O(nlogn) operations.Explanation / Answer
Begin:
for i=1 to n do
for j=1 to n do
Turn switches j to n/2 ON
Test wire i
If lamp lights up
Set n <- n/2
Else
Set j <- (n/2 +1)
Turn all switches OFF
End for j
End for i
End
When you apply the above algorithm you will find a scenerio when the testing wire is connected with one switch ON and lamp lights up.
This algorithm will give you O(nlogn) complexity.
Explanation:
For testing each wire n iteration is required (loop i)
For testing switches for every i, total switches are divided into two halves. One half will glow the lamp and the other half will not glow the lamp. So, one half will be discarded and the process repeats untill you find one switch which is glowing the lamp.
If the inner loop takes k iteration
Then 2k=n
So, k=log2n
So, overall time complexity O(nlog2n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.