Wednesday, November 19, 2008

Finding the Nth open door

As a follow up to my previous post about the 100 Door Puzzle, I realised there is a variation of the question where there is an even faster answer.

If the question is: which door is the nth open door (for example tell me where the 5th open door is) then the answer is: n2 or as per the example 52=25 (the 25th door along is the 5th open door)

private static int NextOpenDoorIsAt(int nthOpenDoor)
return (int)Math.Pow(nthOpenDoor, 2d);

So in the case where you only need to find the nth door that is open this is a faster method. This of course could be applied to my previous post to give an O(√N) solution for the whole series - the faster being down to the speed of summation vs. product.

No comments: