ven a black box that con witches. Each wire is con You are gi nects n wires to n
ID: 3593998 • Letter: V
Question
ven a black box that con witches. Each wire is con You are gi nects n wires to n s nected to exactly one s to zero or 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 witch. Each switch is connected more wires. Your goal is to Wires Switches It is easy to discover all the connections using O(n2) operations, as follows. Initially, turn all the switches off (n operations) for i:= 1 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 2 1s connected to switch Turn switch 7 off Give an algorithm which discovers all the connections using O(nlogn) operations.Explanation / Answer
Solution:
From O(n2 ) to O(nlogn) , we can reduce complexity by efficient Search of wire.
In starting , while making the connection we will do some task :-
Given n switches and n wires
1. we will give unique number to all switch (ie 1 to n) .
2. And also give number to wire which which it is connected
example: -
If we consider questions example (above) then numbering would be :
wire switch
3 1
1 2
3 3
Now ,
sort wire
wire switch
1 1
3 2
3 3
Now we can choose one switch (k) and make binary search on the same(k) number , if it is found then connection with that wire else not connectectd with that wire we will do for all switch.
one Searching will take O(logn) time and for n it will take O(nlogn).
Hence we will successfully reduced its complexity from O(n2 ) to O(nlogn).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.