Let's think about the problem statement more, what do we have?

We have a set of 9 clocks that we want them all to show 12 o'clock and we have a set of 9 different keys that we can push to change the time of a subset of clocks. For example key #1 can change the time of clocks ABDE, so if you press key #1 then clocks labeled A, B, D and E will show a new time which is 3 hours plus their previous time.

If you don't observe any facts in the problem statement, This problem can be modeled as a graph which you want to go from a 'start' node to a 'destination' node, and can be solved using BFS. How many nodes do we have? By 'node' I mean a set of 9 clocks each of which shows a specific time (12-3-6-9), so each clock has 4 situations and the number of nodes is equal to 4*4*...*4 = 4^9 = 262144 that's not too many for a graph to run BFS on it. So you run BFS from the start node and try to reach node(12,12,12 --- 12,12,12 --- 12,12,12) How many neighbors does a node have? Each node has 9 other neighbors through 9 different keys.

But as I told if you observe a simple fact you can see that each key has 4 different situations, so instead of running BFS to find the solution you can use recursion to decide how many times you want to push key #i, and check if you can change all the clocks to show 12 o'clock. I myself think the second solution is more cute than the first solution, there is also another solution which takes O(1) and needs much more insight about the problem.

did not quite get this, can you please elaborate?

ReplyDelete