Just for curiosity, I coded both solution on Matlab and measured the performance of both algorithms (for 365 bulbs). The first one took 0.019566 seconds to complete. The second one (aka, the optimized version ;-) ) took exactly 0.000344 seconds. Maybe not a big deal for 365 bulbs but as you said, if we think bigger the difference is huge!

Keep the puzzles coming ;-) Happy Holidays!

That's true, hehe... My first solution was very similar to yours, then I tried to improve it and took a paper and a pen, I was trying to extract a rule to determine the amount of divisors of a given number. In this problem, we will have ON at the end all those bulbs tagged with a number that has an odd amount of divisors (whatever they are).

In most cases, a number has an even number of divisors, because they are grouped in multiplications.

For instance, the number 50:

1x50; 2x25; and 5x10;

We have 3 multiplications, then, we have 6 divisors.

The perfect squares have an integer square root, so, we have an even number of multiplication factors but one of those multiplications is formed by only one number mutiplied by itself. Then, a perfect square will always have an odd number of divisors, and will remain ON at the end of this problem :-)

Consider 100:

1x100 (we should switch the bulb on day 1 and 100)

2x50 (two more swtchings)

4x25 (two more)

5x20 (two more)

10x10 (one more, the square root)

Number 100 has 9 divisors.

Tomorrow a new puzzle, cheers! :-)

That is much better folk :-)

So, the basic solution could be something like this:

int i=1;

while(i*i<=limit){

       bulbsOn[i]=i*i;

       i++;

}

This gives you a sqrt(n) complexity. You will only have 10 steps for 100 bulbs, 1000 for 1,000,000 bulbs...

What about a more efficient solution? Tip: Dynamic programming ;-)

And, in conclusion: Which is the moral of this problem?

You, like I did the first time and most of people trying to solve this problem, have tried to code before trying to find the optimal approach for the problem.

A very wise friend of mine said one time: "When you have a hammer, everything seems a nail to hammer in"

We use to talk about high-level languages, like C#, Java... We use to add even more libraries or namespaces to these languages, very powerful libraries and languages...

But we shouldn't forget that the most powerful weapons that humans have are mathematics and logic ;-)

Next puzzle in a few days, I am glad you liked this one :-)

Good solution: you have found the correct bulbs... Congrat!! :-)

Regarding to the algorithm, I have a complexity of sqrt(n) for the first execution, that could also be improved for next executions changing the size of the problem (number of bulbs and days) if we use dynamic programming...

I will give you just one more clue: those numbers are special from a mathematical perspective ;-)

Yes, it will be 19 bulbs ON... But the most important: which is the method?

Even more important: which is the most efficient method? Which is the complexity?

And the last one (if you get the most efficient method, you will know this one): which bulbs (#1, #2 or whatever) will be ON?

Good job sriram, I think you are on the way (but I don't know your method, so... hehe)

Mmm, no... Probably my explanation is not very good. This is a more complete example:

Day 1: You switch (ON) all the bulbs multiple of 1, so... 1,2,3,4...365

Day 2: You switch (OFF, because they were ON) all the multiples of 2: 2, 4, 6...

Day 3: You switch all the bulbs multiple of 3: number 3 OFF (it was ON since first day), number 6 ON (it was OFF since day 2), number 9 OFF (it was ON since first day...)

Knowing the method, I can say you that, in day, 183 there will be more than 13 bulbs ON (I can say also which ones, but it will be too much easy for you to solve it with that clue)...

Good luck ;-)