Difficulty: Medium, Asked-In: Microsoft, Bloomberg
There is a circle of n lights with a switch next to each of them. Each switch can be flipped between two positions, thereby toggling the on/off states of three lights: its own and the two lights adjacent to it. Initially, all the lights are off. How can we design a strategy to turn all the lights on by flipping the minimum number of switches?
After reading the problem statement, the simplest thing we can do is try out some sample test cases and figure out if any pattern exists.
Trial 1: Let’s take n = 6: if we switch on the two bulbs as shown in the image below, all the bulbs will be switched on. But what sense this trial makes. Let’s see.
We can observe from here if for any n if we can group three such bulbs, then we can switch it on in a single go. Thus we can divide this problem into three sub-problems:
In this case, we can group three bulbs together and switch them on one by one. So for n = 6, we need two steps to switch on all the bulbs. Similarly, for any n divisible by 3 we need n/3 steps to switch on all the bulbs.
Let’s take one example to n = 7 bulbs as 7%3 = 1. Now figure out how things are working. Initially, all the bulbs are switched off. Before switching any bulb, let’s think about the strategy we must follow for switching on or off any bulb. As already we have seen in the previous case, if we have a number of bulbs which is multiple of three, we can switch it on all by grouping them in the group of 3. In this particular bulbs combination, if we group 3 bulbs together and switch them on, we will always be left with one bulb. Let’s think in a reverse way: if we could manage to switch it on that one bulb, the remaining will be switched on in one go. Try to do it yourself :) !!
So let’s discuss how we will proceed. We can follow along with the image posted below. First, we will switch on all the bulbs numbered 1 to 6, which would take 2 steps. Now our goal would be to switch on the remaining single bulb. How do we do it? Let’s think!
So, a total of 7 steps we have required to turn all the bulbs.
So generalizing this fact we required n steps for turning on all the bulbs such that n%3 =1. How? let’s think! Suppose n= 3k + 1.
So when n%3 = 1, the total number of steps to turn on all the bulbs = k+ (k + 1) + k = 3k + 1 = n
For this last case, let’s take one example: n = 8 bulbs as 8%3 = 2. Let’s figure out how things will work in this case. Initially, all the bulbs are switched off as usual. Again before switching any bulb, let’s think about the strategy. In this particular bulbs combination, if we group 3 bulbs together and switch them on, we will always be left with two bulbs. What if we think in a reverse way: if we find a way to switch on those two bulbs, the remaining will be switched on in one go. Try to do it yourself :) !!
Let’s discuss how we will proceed in this case. First, we will switch on all the bulbs numbered 1 to 6, which would take 2 steps. Now our goal would be to switch on the remaining 2 bulbs. How do we do it? Let’s think!
Finally, we can switch on the remaining 6 bulbs in 2 steps.
Now the interesting thing is we required only 8 steps to do so: 2 steps to turn on 6 bulbs + 1 for turning on the 8th bulb + 2 steps to turn off the 2nd and 6th bulb + 1step to turn on the 7th bulb + 2 steps to turn on the remaining bulbs.
Again we can generalize that for n such bulbs, we require a minimum of n steps to turn all the bulbs on where n%3 = 2. let’s think! Suppose n= 3k + 2.
So when n%3 = 2, the total number of steps to turn on all the bulbs = k+ (k + 2) + k = 3k + 2 = n
This generalization is due to the strategy we are following i.e. to lit 2 adjacent bubs and the remaining (N-2) will always be divisible by 3.
Now from all three cases, we can finally conclude that it requires N/3 steps to lit all the bulbs if N is divisible by 3 else we will require N steps always.
Enjoy learning, Enjoy Mathematics!
There are n+1 people at a party. They might or might not know each other names. There is one celebrity in the group, and the celebrity does not know anyone by their name. However, all the n people know that celebrity by name. You are given the list of people present at the party. And we can ask only one question from each one of them. “Do you know this name”? How many maximum numbers of questions do you need to ask to identify the actual celebrity?
You’ve got someone working for you for seven days and a gold bar to pay him. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. What is the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?
A group of four people, who have one torch, need to cross a bridge at night. A maximum of two people can cross the bridge at one time, and any party that crosses (either one or two people) must have the torch with them. The torch must be walked back and forth and cannot be thrown. Person A takes 1 minute to cross the bridge, person B takes 2 minutes, person C takes 5 minutes, and person D takes 10 minutes. A pair must walk together at the rate of the slower person’s pace. Find the fastest way they can accomplish this task.